Heuristic Search for Multiagent and Factored Planning

Abstract:
Highly informed automatically derived heuristics supporting state-space search stood behind the greatest efficiency improvements of classical planners in recent years. In this project, we propose to follow this successes in distributed multiagent and parallel factored planning. We aim at two state-of-the-art heuristics LM-cut and Merge&Shrink and we plan to theoretically design their distributions efficient in terms of computation and communication complexity. To assess the practical properties, we implement the heuristics and experimentally evaluate them in an adapted distributed search and a novel heuristic scheme on a common set of benchmark planning problems. Especially the experimental results will be further used for efficiency improvements of particular implementations. Finally, we propose to use the results of the previous analyses to theoretically design and to create novel heuristics specific for multiagent and factored planning.

Motivation:
Practical applications of domain-independent planning (incl. multiagent and factored planning) span over wide spectrum of problems from logistics and manufacturing to space missions. A practical motivation of the project is to design, implement and evaluate a novel software planning system usable as a component in other smart technologies, inspiration for domain-dependent implementations or as a tool for decision-support in the mentioned domains.

From: 2015-01-01
To: 2017-12-31

Involved: Antonín Komenda, Michal Štolba, Daniel Fišer