A Robust Planning Algorithm for Groups of Entities in Discrete Spaces

Entropy

Igor Wojnicki²  Sebastian Ernst¹  Wojciech Turek² 

[1] AGH University of Science and Technology, Al. Mickiewicza 30, Kraków, 30-059, Poland;

关键词: artificial intelligence;    heuristic search;    automated planning;    robotics;    multi-entity coordination;   

DOI  :  10.3390/e17085422

来源: mdpi

【 摘 要 】

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.

【 授权许可】

CC BY   
© 2015 by the authors; licensee MDPI, Basel, Switzerland.