A Robust Planning Algorithm for Groups of Entities in Discrete Spaces

作者：Wojnicki Igor; Ernst Sebastian^*; Turek Wojciech

来源：Entropy, 2015, 17(8): 5422-5436.

DOI：10.3390/e17085422

Automated planning is a well-established field of artificial intelligence (AI), with applications in route finding, robotics and operational research, among others. The task of developing a plan is often solved by finding a path in a graph representing the search domain; a robust plan consists of numerous paths that can be chosen if the execution of the best (optimal) one fails. While robust planning for a single entity is rather simple, development of a robust plan for multiple entities in a common environment can lead to combinatorial explosion. This paper proposes a novel hybrid approach, joining heuristic search and the wavefront algorithm to provide a plan featuring robustness in areas where it is needed, while maintaining a low level of computational complexity.

• 出版日期2015-8