Motion Planning For Multi-Robot Formation

In real application, many tasks need cooperation of multi robots. Multi-robot sys-tem have several good properties that single complex robot may not have. Thus it ispossible to handle tasks more efciently. In many cases, multi robots are required toform certain formation to fulfll the formation task. During the recent decade, many re-search work devoted to multi-robot navigation. However, research works about motionplanningofformationarerelativelyrare. Andalltheseresearchworkassumesthattaskis feasible. When the task is infeasible, these method can’t turn it into a feasible onewhile ensuring the task objective is fulflled. In the mean time, research works aboutturningtheinfeasibletaskareonlyapplicabletosinglerobot. Andonlytheinformationaboutwhytheistaskinfeasiblecanbefound. Noguidelinescanbeprovidedabouthowto modify these constraints.In this paper, we investigate the problem of task oriented motion planning ofmulti-robot formation. The objective is to maintain formation constraint and colli-sion avoidance of individual robot at the same time. The representation space modelof multi-robot formation is built to characterize the process of performing formationnavigation task. A hierarchical structure is proposed to realize the model. Based onthis results, task related constraints are analyzed. And motion planning algorithms arereviewed to solve the planning problem in representation space. Simulation results areprovide to prove the statements. The research work can be classifed into the followingaspects:(1) Summary of representation space is provided. The motivation and idea ofrepresentation space is clearly stated. Based on the process of turning the infeasibletask towards feasible, the task oriented motion planning framework is proposed.(2) By combining motion planning with task, the representation space model ofmulti-robot formation is built to characterize the process of performing formation task. Basedonwhich, ahierarchicalstructureisproposedtoensurethatformationconstraintandcollisionavoidanceismaintainedduringthetaskrealization. Thentheexternalandinternal constraints are analyzed in the formation task.(3) Firstly the problem of whether a task is feasible is translated to completenessof planning algorithms in representation space. Secondly, optimality of planning algo-rithmsareanalyzedtoproducetheoptimalpathoffulfllingtask. Someotherpropertiesofplanningalgorithmsarealsoevaluated. Thenthealgorithmsthatcanbeusedtosolvethe motion planning problem in representation space are provided.(4) The simulation of7robots forming a triangle formation navigating in a ware-house environment is conducted. Which show that infeasible task can be turned to afeasible one if the formation shape constraint is modifed. Another simulation of27robots in a rectangle formation navigating in the warehouse with a movable obstacle isprovide to show that the proposed method can be used to satisfy formation constraintand collision avoidance at the same time. And, when the task is infeasible, the task ori-ented motion planning framework can be used to turn the infeasible task into a feasibleone while ensuring that task objective is reached.