A Robust Planning Algorithm for Groups of Entities in Discrete Spaces
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 nu...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2015-07-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1099-4300/17/8/5422 |
| _version_ | 1817993419084005376 |
|---|---|
| author | Igor Wojnicki Sebastian Ernst Wojciech Turek |
| author_facet | Igor Wojnicki Sebastian Ernst Wojciech Turek |
| author_sort | Igor Wojnicki |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-14T01:39:33Z |
| format | Article |
| id | doaj.art-843ab729b0a746cc887a3edfbb969c54 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-14T01:39:33Z |
| publishDate | 2015-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-843ab729b0a746cc887a3edfbb969c542022-12-22T02:19:49ZengMDPI AGEntropy1099-43002015-07-011785422543610.3390/e17085422e17085422A Robust Planning Algorithm for Groups of Entities in Discrete SpacesIgor Wojnicki0Sebastian Ernst1Wojciech Turek2AGH University of Science and Technology, Al. Mickiewicza 30, Kraków, 30-059, PolandAGH University of Science and Technology, Al. Mickiewicza 30, Kraków, 30-059, PolandAGH University of Science and Technology, Al. Mickiewicza 30, Kraków, 30-059, PolandAutomated 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.http://www.mdpi.com/1099-4300/17/8/5422artificial intelligenceheuristic searchautomated planningroboticsmulti-entity coordination |
| spellingShingle | Igor Wojnicki Sebastian Ernst Wojciech Turek A Robust Planning Algorithm for Groups of Entities in Discrete Spaces Entropy artificial intelligence heuristic search automated planning robotics multi-entity coordination |
| title | A Robust Planning Algorithm for Groups of Entities in Discrete Spaces |
| title_full | A Robust Planning Algorithm for Groups of Entities in Discrete Spaces |
| title_fullStr | A Robust Planning Algorithm for Groups of Entities in Discrete Spaces |
| title_full_unstemmed | A Robust Planning Algorithm for Groups of Entities in Discrete Spaces |
| title_short | A Robust Planning Algorithm for Groups of Entities in Discrete Spaces |
| title_sort | robust planning algorithm for groups of entities in discrete spaces |
| topic | artificial intelligence heuristic search automated planning robotics multi-entity coordination |
| url | http://www.mdpi.com/1099-4300/17/8/5422 |
| work_keys_str_mv | AT igorwojnicki arobustplanningalgorithmforgroupsofentitiesindiscretespaces AT sebastianernst arobustplanningalgorithmforgroupsofentitiesindiscretespaces AT wojciechturek arobustplanningalgorithmforgroupsofentitiesindiscretespaces AT igorwojnicki robustplanningalgorithmforgroupsofentitiesindiscretespaces AT sebastianernst robustplanningalgorithmforgroupsofentitiesindiscretespaces AT wojciechturek robustplanningalgorithmforgroupsofentitiesindiscretespaces |