Multi-robot path planning is dificult due to the combinatorial explosion of the search space with every new robot added. Complete search of the combined state-space soon becomes intractable. In this paper we present a novel form of abstraction that allows us to plan much more eficiently. The key to this abstraction is the partitioning of the map into subgraphs of known structure with entry and exit restrictions which we can represent compactly. Planning then becomes a search in the much smaller space of subgraph configurations. Once an abstract plan is found, it can be quickly resolved into a correct (but possibly sub-optimal) concrete plan without the need for further search. We prove that this technique is sound and complete and demonstrate its practical effiectiveness on a real map. A contending solution, prioritised planning, is also evaluated and shown to have similar performance albeit at the cost of completeness. The two approaches are not necessarily conflicting; we demonstrate how they can be combined into a single algorithm which out-performs either approach alone.
@cite_19: The warehouseman's problem, namely, the coordinated motion planning for multiple independent objects confined in a room, is addressed. Several constraints are presented under which the problem becomes tractable, and polynomial time algorithms that guarantee a coordinated rearrangement under the given conditions are obtained. The concept of temporary storage space (TSS) is introduced as a general way of constraining free space. Each algorithm presented has a different set of constraints on the possible sizes and or relative placements of the square blocks. For each case, an adequate TSS is proposed that guarantees rearrangement of n blocks through algorithms having O(n sup 2 ) running time. The practical utility of the presented techniques is also discussed in the light of the complexity of motion coordination. >
@cite_9: This work makes two contributions to geometric motion planning for multiple robots: i) motion plans can be determined that simultaneously optimize an independent performance criterion for each robot; ii) a general spectrum is defined between decoupled and centralized planning. By considering independent performance criteria, we introduce a form of optimality that is consistent with concepts from multi-objective optimization and game theory research. Previous multiple-robot motion planning approaches that consider optimality combine individual criteria into a single criterion. As a result, these methods can fail to find many potentially useful motion plans. We present implemented, multi-robot motion planning algorithms that are derived from the principle of optimality, for three problem classes along the spectrum between centralized and decoupled planning: i) coordination along fixed, independent paths; ii) coordination along independent roadmaps; iii) general, unconstrained motion planning. Several computed examples are presented for all three problem classes that illustrate the concepts and algorithms.
@cite_20: Current research in self-reconfiguring robots focuses predominantly on systems of identical modules. However, allowing modules of varying types, with different sensors, for example, is of practical interest. In this paper, we propose the development of an algorithmic basis for heterogeneous self-reconfiguring systems. We demonstrate algorithmic feasibility by presenting O(n sup 2 ) time centralized and O(n sup 3 ) time decentralized solutions to the reconfiguration problem for n non-identical modules. As our centralized time bound is equal to the best published homogeneous solution, we argue that space, as opposed to time, is the critical resource in the reconfiguration problem. Our results encourage the development both of applications that use heterogeneous self-reconfiguration, and also heterogeneous hardware systems.
Other faster solutions to the multi-robot problem are available if we can assume the existence of garage'' locations for each robot @cite_9 or other kinds of temporary free space @cite_19 @cite_20 . The method we present here makes no such assumption and is thus more general in application. There does not appear to be any previous work which provides a complete abstraction-based planner for the general multi-robot problem.