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.
Abstraction and hierarchical decomposition are standard techniques in planning and other related search problems. The use of macro-operators dates back as far as Sacerdoti's early work on the planning system @cite_15 which introduced abstraction hierarchies, whereby a problem could first be solved at a high level of abstraction while ignoring lower-level details. The idea has been re-expressed in many different ways through the history of planning -- far too many to review in detail. This present work was particularly inspired by the generic types' of longfox02 in which they similarly detected substructures in a task-planning problem and solved them using structure-specific planners.
@cite_15
2160386431 128952136 2135939055 2401064609
An abstraction of a problem of rearranging group of mobile robots is addressed in this paper (the problem of multi-robot path planning). The robots are moving in an environment in which they must avoid obstacles and each other. An abstraction where the environment is modeled as an undirected graph is adopted throughout this work. A case when the graph modeling the environment is bi-connected is particularly studied. This paper puts into a relation the well known problems of moving pebbles on graphs (sliding box puzzles) with problems of multi-robot path planning. Theoretical results gained for problems of pebble motion on graphs are utilized for the development of algorithms for multi-robot path planning. As the opti-mization variant of both problems (a shortest solution is required) is known to be computationally hard (NP-hard), we concentrate on construction of sub-optimal solving procedures. However, the quality of solution is still an objective. Therefore a process of composition of a sub-optimal solution of the problem (a plan) of the pre-calculated optimal plans for the sub-problems (macros) is suggested. The plan composition using macros was inte-grated into two existing sub-optimal solving algorithms. In both cases, substantial improvements of the quality of resulting plans were achieved in comparison to the origi-nal algorithms. The no less important result is that one of the existing algorithms was generalized by integrating macros for larger class of problems of multi-robot path planning. Abstraction, in search, problem solving, and planning, works by replacing one state space by another (the "abstract" space) that is easier to search. The results of the search in the abstract space are used to guide search in the original space. For instance, the length of the abstract solution can be used as a heuristic for A* in searching in the original space. However, there are two obstacles to making this work efficiently. The first is a theorem (Valtorta, 1984) stating that for a large class of abstractions, "embedding abstractions," every state expanded by blind search must also be expanded by A* when its heuristic is computed in this way. The second obstacle arises because in solving a problem A* needs repeatedly to do a full search of the abstract space while computing its heuristic. This paper introduces a new abstraction-induced search technique, "Hierarchical A*," that gets around both of these difficulties: first, by drawing from a different class of abstractions, "homomorphism abstractions," and, secondly, by using novel caching techniques to avoid repeatedly expanding the same states in successive searches in the abstract space. Hierarchical A* outperforms blind search on all the search spaces studied. 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. Large-scale classical planning problems such as factory assembly problems pose a significant challenge for domain-independent planners. We propose a macro-based planner which automatically identifies subproblems, generate macros from subplans and integrate the subplans by solving the whole augmented problem. We show experimentally that our approach can be used to solve large problem instances that are beyond the reach of current state-of-the-art satisficing planners.