[机械模具数控自动化专业毕业设计外文文献及翻译]【期刊】协同多车编队铲雪应用于机场-外文文献

Intel Serv Robotics (2009) 2:205217DOI 10.1007/s11370-009-0048-5SPECIAL ISSUEApplication of coordinated multi-vehicle formations for snowshoveling on airportsMartin Hess Martin Saska Klaus SchillingReceived: 13 March 2009 / Accepted: 6 August 2009 / Published online: 23 August 2009 Springer-Verlag 2009Abstract Inthispaper,wepresentaframeworkthatappliesmultiple groups of autonomous snowplow robots for effi-ciently removing the snow from airfields. The main idea is toform temporary coalitions of vehicles, whose size dependson the width of the roads to clean. The robots of a coalitionthenarrangeinformationandaccomplishassignedsweepingtasks. In the paper the problem of snow shoveling is dividedinto the subproblems of task allocation and motion coor-dination. For the task allocation we propose a multi-agentmethod designed for the dynamic environment of airports.The motion coordination part focuses on generating trajec-tories for the vehicle formations based on the output of thetaskallocationmodule.Furthermoreaspecificfeedbackcon-troller is introduced that achieves optimal breadthwise roadcoverage even in sharp turns. All components as well as thecomplete system have been verified in various simulations.Additionally the motion coordination approach was tested inlaboratory hardware experiments.Keywords Multi-vehiclesystemsCooperativesweepingTask allocation Motion planning Motion controlParts of the article have been published before in the proceedings ofinternational conferences 14,29,30.M. Hess (B) K. SchillingComputer Science VII: Robotics and Telematics,University of Wuerzburg, Wrzburg, Germanye-mail: m.hessinformatik.uni-wuerzburg.deK. Schillinge-mail: schiinformatik.uni-wuerzburg.deM. SaskaDepartment of Cybernetics, Faculty of Electrical Engineering,Czech Technical University, Prague, Czech Republice-mail: saskalabe.felk.cvut.cz1 IntroductionDuring the winter months snowy weather has a huge influ-ence on an airports usual workflow. The air traffic needs tobe interrupted from time to time in order to sweep away thesnowfromtheairfield.Thisiscrucialsincesnowisapotentialrisk for starting and landing aircrafts. Today the tracks of anairport are usually freed from snow by utilizing a fleet ofhuman driven snowplows. Recent technological advances inthe field of mobile robotics enable to set up a multi-vehiclesystem consisting of groups of autonomous snowplows forthis task. By arranging the vehicles in formations and apply-ing coordinated task allocation such a system could signifi-cantly reduce the time of interrupted airport traffic. Relatedsweeping approaches lack robustness or rely on simplifica-tions of the problem that make them unusable for the airportsweeping problem (cf. e.g. 18,20,26,33).In the framework presented in this paper we utilizeformations of autonomous car-like robots. The majority ofapproaches for formation control can be classified into threemain branches: virtual structures, behavioral techniques, andleader-followingmethods.Inthevirtualstructureapproachesthe entire formation is treated as a single rigid structurewhere each vehicle applies a certain control in order to trackthe desired trajectory and simultaneously maintain the rigidstructure 7,21. In behavior based methods (cf. e.g. 5,23)each agent follows multiple objectives (behaviors) and theactual control is derived as a weighted average, where theweights are assigned with respect to the importance of eachtask 22,28. In leader-following approaches, one or morepossiblyvirtualrobotsaredesignatedasleaders.Thefollowerrobots try to maintain their position in the formation relativeto the leader vehicles. For this the leaders configuration istransmitted to the followers via wireless communication orit may be obtained by means of active sensing 9,16.123206 Intel Serv Robotics (2009) 2:205217From an application point of view the addressed snowshoveling task is related to the field of autonomous sweep-ing. Its aim is to find and execute a motion for the robots inorder to cover a predefined area by their effector.1For coop-erative sweeping it is often desired to coordinate the vehiclesin a time-optimal way.Kurabayashi et al. addressed the problem of cooperativesweeping by generating a path for a single robot, which isthen segmented and distributed among the vehicles 20. Thesame group extended the approach with the robots ability torelocatemovableobstaclesin4,19.Incontrasttothis,Wag-ner et al. proposed an ant-like strategy for the cooperativecleaning of an unknown non-convex grid-map region 33.The homogeneous robots with a limited amount of mem-ory follow only local rules, what makes the method fullydecentralized. Another decentralized approach using an on-line negotiation mechanism to resolve the task sharing wasproposed in 27. For this market-based strategy the authorsassume that all-to-all communication is available. In 18theauthors use a partitioning algorithm that divides the area toclean into a finite number of polygons. These are then allo-cated among the robots in a decentralized fashion. Both, thedetermination of the subareas and their assignment are doneduring the cleaning. Luo et al. developed a real-time methodbased on biologically inspired neural networks where eachrobottreatstheotherrobotsasmovingobstacles25,26.Thesweeping of dynamic materials is investigated in 3. Hereit is assumed, that the material to clean spreads within thegrid-based map. In 2 the authors propose a decompositionof the sweeping task by partitioning the area that is supposedto be cleaned. The approach is characterized by its focus onrealizability, which is demonstrated in an experiment withreal robots.Projecting the problem of cooperative sweeping onto theairfield, the snow shoveling task generates some problemsthathavenotyetbeenaddressedinthatcontext.Theapproachdescribed in the following considers the nonholonomic kine-matics of usual snowplows as well as position and orienta-tion of the plows shovels. Furthermore, the working spaceis more structured due to the airfield environment. Anotherproblem lies in the fact that all methods mentioned abovelack the ability to react on sudden changes in the environ-ment, which is important for robust and safe execution of thesweeping process.The first problem to solve now is to assign a task to eachsnowplow about when to clean which parts of the airfield.Sincepartlycleanedroadsegmentscouldbedangerousespe-cially in emergency situations, we require that the main run-ways as well as the auxiliary roads are cleaned up at once bya sufficiently big group of vehicles. Thus, we avoid forcinglanding planes as well as rescue and fire fighting vehicles1In our case these are the snowplows shovels.facing roads with a irregular snow surface. The utilized taskallocation method applies simple heuristics and an algorithmfor systematically exploring a part of the tree of solutions.This strategy provides fast responses at the expense of possi-bly missing optimality. Therefore it allows the task list to becomputed online and to be adjusted on the fly e.g. in order toreact on unforeseen events.Thesecondsubproblemishowtotranslatetheinstructionsfrom the task list into commands for the low level controlof the vehicles. For this we utilize a method that constructstraceable trajectories for the reference points (leaders) of thesnowplowformations.Totrackthesetrajectorieswiththefor-mations we apply a leader following approach that maintainsthe arrangement of the group in curvilinear coordinates. Onthe lowest level of control each robot implements a feedbackcontrollerthattracksitsindividualdesiredtrajectorywiththemountingpointofitsshovelresultinginoptimalbreadthwisecoverage of the road.The developed methods have been intensively tested invarious simulations as well as in laboratory hardware exper-iments. Frankfurt international airport, which is one of thelargest airports in Europe was chosen as a testing scenariofor the proposed task allocation algorithm. But since the ap-proach does not rely on a specific airport structure, it caneasily be applied to other airports as well.The remainder of this paper is organized as follows.Section 2 gives an overview of the overall snow shovelingsystem. In Sect. 3 we describe the design of our task allo-cation approach. After this, we introduce suitable motioncoordinationtechniquesforthevehicleformationsinSect.4.Results from the hardware experiments and simulations arepresented in Sect. 5. Finally we give some concludingremarks in Sect. 6.2 System overviewIn this section we describe the system structure of our ap-proach. We decided to rely on central supervision for thehigh level coordination of the system. The main reason forthis is safety, since a central command center has a completeoverview of the whole system. The single point of failureproblem, which arises from a single command center, can besolved by one or two redundant command center units thattake over in case of a failure. Another reason for the cen-tralized approach is that the workspace of the robots is wellknown in size and structure. Therefore the scalability pro-vided by a decentralized approach with agents exchangingparts of the map etc. is not necessary. Another drawback ofa decentralized system would be the additional time neededfor the sweeping process, since the task allocation has to relyon less information.123Intel Serv Robotics (2009) 2:205217 207The highest level of the proposed scheme (see Fig. 1)isdivided into two types of units. The first one, which we callthe Command Center, is responsible for the central tasks.The second kind of unit (blocks denoted as Formation I toFormationM)representsthecurrentconstellationofvehicleswhere each unit corresponds to one formation. These units,which are independent from the Command Center most ofthe time, primarily are responsible for putting the assignedtask into the appropriate formation motion.The core of the Command Center is the Task Allocationmodule that utilizes two data structures: MAP and GRAPH.The MAP-structure consists of the vector-based representa-tion of the borders of the area that needs to be cleaned. Fur-ther it contains information about known obstacles as well asthecoordinatesutilizedtoconstructthereferencetrajectoriesfor the snowplow formations. The GRAPH data structure ispreparedoff-linefromtheMAPbyassigningnodesforeveryintersection and edges for every road in between. Further-more, we assign two numbers to the edges of the graph: thefirst is an integer value equal to the number of plows neededfor the sweeping of the corresponding road and the secondnumber is equal to the roads length, which is assumed tobe proportional to the necessary cleaning time. These valuesare used by the Task Allocation module in order to generatea reasonable output. Additionally we assign a flag to eachedge that marks the already cleaned roads. In contrast to thestaticMAP,theGRAPHstructurecanbeadjustedbyahumanoperator who might close and reopen specific road segmentsaccording tothecurrentairporttraffic.Alsoplowsthatdetectan obstacle on the airfield are meant to update the GRAPHstructure. For the experiments described in this paper bothstructureswerecreatedmanually.Neverthelessitshouldalsobepossibletogeneratethemautomaticallybyapplyingimageprocessing techniques to an aerial photograph or a blueprintof the airfield.The current GRAPH structure is used as an input for theTask Allocation module that will be described in detail inSect. 3. An execution step of the Task Allocation moduleis triggered by snowplows that just accomplished (or failed)their current task, so they are waiting for new instructions.Besides the GRAPH, the module maintains actual plans ofallcoalitionsaswellasaprioritysettingforeachroad,whichdependsontheairporttrafficaswellasonthesnowinginten-sity. Note that the priority setting is not investigated in detailin this article but further information on this topic can befound in 30.In the Formation units the Leader robot is responsible forgenerating a reference trajectory at the beginning of eachtask. This is done with the information received from theTaskAllocationmoduleandtheappropriatecoordinatesfromthe MAP structure. The Leader robot is just one designatedrobot in the formation, usually the one in front of the unit.Besides the snow shoveling the Leader acts as a connectionbetween the robots of its formation and the Command Cen-ter.ItinformstheCommandCenteraboutdetectedobstacles,finished or aborted tasks, as well as the need for additionalrobots to compensate for failures. Note that the Leader robotis not meant to be the reference point in terms of the forma-tion movement, in which it acts like the other robots of thegroup. The individual control inputs in order to follow thereference trajectory while maintaining the formation are cal-culated separately by each follower, where the Leader robotprovides a signal for synchronization. As a result the Forma-tion units are independent from the Command Center mostof the time. Further details about the motion coordinationwill be presented in Sect. 4.Fig. 1 Scheme of the completesnow shoveling system. Thearrows denote communicationlinks between the differentmodulesGRAPHMAP+TaskAllocationRobot1I.RobotI.2RobotI.mRobot1II.RobotII.2RobotII.mRobot1M.RobotM.2RobotM.m.Leader. .I II MFormation I Formation II Formation MLeader Leader123208 Intel Serv Robotics (2009) 2:2052173 Task allocationThe highest reasoning level in the system is an algorithmfor designing a sequence of cleaning tasks for the autono-moussnowplows.Thetaskallocationapproachdevelopedforthe specific application of autonomous multi-vehicle snowshoveling is based on forming temporary coalitions of plowsfor each specific task. The decision of which route will becleaned by which robots is based on a heuristic approachcombined with a partly explored tree of solutions. There isno guarantee that this method finds the global optimal solu-tion, but the fact that the decisions are made immediatelyallows the robots to respond to sudden changes in the envi-ronment. In the remainder of this section we give a shortoverview of related work before we describe the basic ideasof the proposed task allocation approach (cf. also 30).3.1 Related workAccordingtothecommonlyusedtaxonomyoftaskallocationin multi-robot systems published in 13 the problem men-tionedaboveisST-MR-TA:Single-Taskrobots,Multi-Robottasks, Time-extended Assignment. ST means that each robotis capable of executing one task at a time, MR means thattasks require multiple robots and TA means that informationfor future planning is available. This class of tasks includescoalitionformationandschedulinganditbelongstotheclassof NP-hardproblems(cf.12).Anexample forcooperativecoalition formation can be found in 1 where an underlyingorganization is used to guide the formation process. More-overareinforcementlearningtechniqueisappliedtoincreasethequalityoflocaldecisionsasagentsgainmoreexperience.A local learning strategy for improving the aggregate perfor-mance of sensor network agents also has been used in 8.Another approach designed for reconnaissance scenarios,where a team of scout robots observe several areas of inter-est, solved the task allocation problem using a market-basedstrategy 34. In the investigated scenario, each area can beseen from a set of observation points, thus enabling a taskdecomposition. In contrast to our algorithm each task doesnot necessarily needs to be accomplished at once, but differ-ent observation points of the same area could be visited sub-sequently.Morerelatedtoourworkistheapproachaddressedin 32, where a MT-MR-problem is investigated. The objec-tive was to assign robot teams to certain tasks such that thesystems overall efficiency is maximized. To achieve this,the authors used heuristics to find approximate solutions andadjusted them for application in box pushing, room cleaningor sentry duty applications. One of the contributions of ourapproach is the design of appropriate heuristics combinedwith a partly expanded tree of solutions, which yields a localoptimal solution for our specific task allocation problem.3.2 HeuristicsIn our method we use a multi-agent approach to describe thebehavior of the plows. In the Task Allocation module eachFormation unit is considered to be one object (agent) withan assigned task. When a cleaning task is finished, the sameagent can only be used for another road, if the number ofplows is still sufficient. If a bigger group is needed for thenew task, the agent has to ask the remaining robots for help.Incontrast,ifthenextroadtocleanisnarrower,theredundantplows will be offered to the other agents.Nowtodecidewhichroadshouldbesweptbywhichagentis the crucial part of this approach. In the first step, a sortedlist Ltisgeneratedthatconsistsofalluncleanedroads(tasks)ordered by the distance from the current mean position of theidling plows to the intersection where sweeping of the cor-responding road would be started. In the second step, freerobots are allocated to the most prioritized roads. For thiswe choose the first N roads from Lt, where N is the biggestinteger satisfyingNsummationdisplayi=1Wi nfr. (1)Here, Widenotes the number of plows needed to accomplishthe ithtask in Ltand nfrdenotes the number of robots thatare currently free.2After this, the free robots are assigned togroups Fisuch thatmaxi=1,.,NparenleftbiggmaxjFiparenleftbigtimei, jparenrightbigparenrightbigg(2)isminimal, where timei, jdenotes the time needed for plow jto move from its actual position to the beginning of road i.Because of the fact that in each task allocation step N 1entries are removed from the nonempty list of uncleanedroads, it is guaranteed that no road will be omitted duringthe cleaning process. The lists sorting rule, which ensuresthat the idling vehicles mean distance to the next uncleanedroadisminimal,ingeneralreducestheprobabilitythatplowshave to move far before they cont