Authors:
(1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento;
(2) Marco Robol, Department of Information Engineering and Computer Science University of Trento;
(3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento;
(4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. 6 Conclusion This work aimed to evaluate the performance of several known heuristic search algorithms, such as D*, D* Lite, LPA*, LRTA*, RTAA*, and ARA* in terms of solving time, memory consumption, and path cost. The evaluation was made using different randomly generated grid environments with different characteristics alongside personalized grid environments with horizontal walls and different wall lengths as different hinders. Our experimental evaluation revealed that all the algorithms exhibit different performances with strengths and weaknesses under different grid characterizations. D* Lite consistently generated the shortest paths even in obstacle-dense grids, indicating its efficiency in dense environments. ARA* consistently provides faster solutions as the grid size increases, particularly larger than 100, while RTTA* generates faster solutions in smaller grid sizes, with the advantage of not being affected by dense environments. Our study provides valuable insights into selecting the appropriate heuristic search algorithm in the pathfinding domain. Using these insights, we propose a selection algorithm used to optimize the performance needed in a pathfinding domain, such as, solving time, path length, or memory consumption. However, our evaluation focused only on static environments, while dynamic environments may introduce additional challenges. Furthermore, we considered a limited set of experiments, not covering all possible combinations of the grid characteristics. This limitation means that the selection algorithm might not always recommend the most optimal solution, as seen in the example we introduced to evaluate our algorithm. In future work, we aim to address these limitations as follows: Firstly, we plan to extend our evaluation of the search algorithms to include dynamic environments. Secondly, we intend to explore various combinations of both domain characterization and priorities. Furthermore, we want to include additional scenario configuration, extending the random obstacles and the walls scenarios. With such additional understanding, we aim to refine our selection algorithm to automatically take decisions among the best search algorithms, based on the type of obstacles in the local search space. References [1] Nafiz Arica, Aysegul Mut, Alper Yörükçü & Kadir Alpaslan Demir (2017): An Empirical Comparison of Search Approaches for Moving Agents. Comput. Intell. 33(3), pp. 368–400, doi:10.1111/coin.12092. [2] Yngvi Björnsson, Vadim Bulitko & Nathan R. Sturtevant (2009): TBA*: Time-Bounded A*. In Craig Boutilier, editor: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, pp. 431–436. Available at http://ijcai.org/ Proceedings/09/Papers/079.pdf. [3] David Bond, Niels A. Widger, Wheeler Ruml & Xiaoxun Sun (2010): Real-Time Search in Dynamic Worlds. In Ariel Felner & Nathan R. Sturtevant, editors: Proceedings of the Third Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, Georgia, USA, July 8 10, 2010, AAAI Press, doi:10.1609/socs.v1i1.18174. Available at http://aaai.org/ocs/index.php/SOCS/SOCS10/paper/ view/2103. [4] Guillaume Brat, Ewen Denney, Dimitra Giannakopoulou, Jeremy Frank & Ari Jónsson (2006): Verification of autonomous systems for space applications. In: 2006 IEEE Aerospace Conference, IEEE, pp. 11–pp, doi:10.1109/AERO.2006.1656029. [5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein (2009): Introduction to Algorithms, 3rd Edition. MIT Press. Available at http://mitpress.mit.edu/books/ introduction-algorithms. [6] A. Elfes (1989): Using occupancy grids for mobile robot perception and navigation. Computer 22(6), pp. 46–57, doi:10.1109/2.30720. [7] Carlos Hernández & Jorge A. Baier (2011): Real-Time Heuristic Search with Depression Avoidance. In Toby Walsh, editor: IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, IJCAI/AAAI, pp. 578–583, doi:10.5591/978-1-57735-516- 8/IJCAI11-104. [8] Mohd Javaid, Abid Haleem, Ravi Pratap Singh & Rajiv Suman (2021): Substantial capabilities of robotics in enhancing industry 4.0 implementation. Cognitive Robotics 1, pp. 58–75, doi:10.1016/j.cogr.2021.06.001. [9] Sven Koenig (2001): Agent-Centered Search. AI Mag. 22(4), pp. 109–132, doi:10.1609/aimag.v22i4.1596. [10] Sven Koenig (2004): A Comparison of Fast Search Methods for Real-Time Situated Agents, pp. 864–871. doi:10.1109/AAMAS.2004.10122. Available at https://doi.ieeecomputersociety.org/10.1109/ AAMAS.2004.10122. [11] Sven Koenig & Maxim Likhachev (2002): D*Lite, pp. 476–483. Available at http://www.aaai.org/ Library/AAAI/2002/aaai02-072.php. [12] Sven Koenig & Maxim Likhachev (2006): Real-time adaptive A*. In Hideyuki Nakashima, Michael P. Wellman, Gerhard Weiss & Peter Stone, editors: 5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006), Hakodate, Japan, May 8-12, 2006, ACM, pp. 281–288, doi:10.1145/1160633.1160682. [13] Sven Koenig & Xiaoxun Sun (2009): Comparing real-time and incremental heuristic search for real-time situated agents. Auton. Agents Multi Agent Syst. 18(3), pp. 313–341, doi:10.1007/s10458 008-9061-x. [14] Richard E Korf (1990): Real-time heuristic search. Artificial intelligence 42(2-3), pp. 189–211, doi:10.1016/0004-3702(90)90054-4. [15] Maxim Likhachev, Geoffrey J. Gordon & Sebastian Thrun (2003): ARA*: Anytime A* with Provable Bounds on Sub-Optimality, pp. 767–774. Available at https://proceedings.neurips.cc/paper/2003/hash/ ee8fe9093fbbb687bef15a38facc44d2-Abstract.html. [16] Manuel Müller, Timo Müller, Behrang Ashtari Talkhestani, Philipp Marks, Nasser Jazdi & Michael Weyrich (2021): Industrial autonomous systems: a survey on definitions, characteristics and abilities. atAutomatisierungstechnik 69(1), pp. 3–13, doi:10.1515/auto-2020-0131. [17] Michal Pechoucek, Simon G Thompson & Holger Voos (2008): Defence Industry Applications of Autonomous Agents and Multi-Agent Systems. Springer, doi:10.1007/978-3-7643-8571-2. [18] Francisco J Perez-Grau, J Ramiro Martinez-de Dios, Julio L Paneque, J Joaquin Acevedo, Arturo Torres-González, Antidio Viguria, Juan R Astorga & Anibal Ollero (2021): Introducing autonomous aerial robots in industrial manufacturing. Journal of Manufacturing Systems 60, pp. 312–324, doi:10.1016/j.jmsy.2021.06.008. [19] José Ricardo Sánchez-Ibáñez, Carlos Jesús Pérez-del-Pulgar & Alfonso García-Cerezo (2021): Path Planning for Autonomous Mobile Robots: A Review. Sensors 21(23), p. 7898, doi:10.3390/s21237898. [20] Anthony Stentz (1995): The Focussed D* Algorithm for Real-Time Replanning. In: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI 95, Montréal Québec, Canada, August 20-25 1995, 2 Volumes, Morgan Kaufmann, pp. 1652–1659. Available at http://ijcai.org/ Proceedings/95-2/Papers/082.pdf. [21] Dmitry S. Yershov & Steven M. LaValle (2011): Simplicial Dijkstra and A* algorithms for optimal feedback planning. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2011, San Francisco, CA, USA, September 25-30, 2011, IEEE, pp. 3862–3867, doi:10.1109/IROS.2011.6095032. This paper is available on arxiv under CC 4.0 license. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. 6 Conclusion This work aimed to evaluate the performance of several known heuristic search algorithms, such as D*, D* Lite, LPA*, LRTA*, RTAA*, and ARA* in terms of solving time, memory consumption, and path cost. The evaluation was made using different randomly generated grid environments with different characteristics alongside personalized grid environments with horizontal walls and different wall lengths as different hinders. Our experimental evaluation revealed that all the algorithms exhibit different performances with strengths and weaknesses under different grid characterizations. D* Lite consistently generated the shortest paths even in obstacle-dense grids, indicating its efficiency in dense environments. ARA* consistently provides faster solutions as the grid size increases, particularly larger than 100, while RTTA* generates faster solutions in smaller grid sizes, with the advantage of not being affected by dense environments. Our study provides valuable insights into selecting the appropriate heuristic search algorithm in the pathfinding domain. Using these insights, we propose a selection algorithm used to optimize the performance needed in a pathfinding domain, such as, solving time, path length, or memory consumption. However, our evaluation focused only on static environments, while dynamic environments may introduce additional challenges. Furthermore, we considered a limited set of experiments, not covering all possible combinations of the grid characteristics. This limitation means that the selection algorithm might not always recommend the most optimal solution, as seen in the example we introduced to evaluate our algorithm. In future work, we aim to address these limitations as follows: Firstly, we plan to extend our evaluation of the search algorithms to include dynamic environments. Secondly, we intend to explore various combinations of both domain characterization and priorities. Furthermore, we want to include additional scenario configuration, extending the random obstacles and the walls scenarios. With such additional understanding, we aim to refine our selection algorithm to automatically take decisions among the best search algorithms, based on the type of obstacles in the local search space. References [1] Nafiz Arica, Aysegul Mut, Alper Yörükçü & Kadir Alpaslan Demir (2017): An Empirical Comparison of Search Approaches for Moving Agents. Comput. Intell. 33(3), pp. 368–400, doi:10.1111/coin.12092. [2] Yngvi Björnsson, Vadim Bulitko & Nathan R. Sturtevant (2009): TBA*: Time-Bounded A*. In Craig Boutilier, editor: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, pp. 431–436. Available at http://ijcai.org/ Proceedings/09/Papers/079.pdf. [3] David Bond, Niels A. Widger, Wheeler Ruml & Xiaoxun Sun (2010): Real-Time Search in Dynamic Worlds. In Ariel Felner & Nathan R. Sturtevant, editors: Proceedings of the Third Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, Georgia, USA, July 8 10, 2010, AAAI Press, doi:10.1609/socs.v1i1.18174. Available at http://aaai.org/ocs/index.php/SOCS/SOCS10/paper/ view/2103. [4] Guillaume Brat, Ewen Denney, Dimitra Giannakopoulou, Jeremy Frank & Ari Jónsson (2006): Verification of autonomous systems for space applications. In: 2006 IEEE Aerospace Conference, IEEE, pp. 11–pp, doi:10.1109/AERO.2006.1656029. [5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein (2009): Introduction to Algorithms, 3rd Edition. MIT Press. Available at http://mitpress.mit.edu/books/ introduction-algorithms. [6] A. Elfes (1989): Using occupancy grids for mobile robot perception and navigation. Computer 22(6), pp. 46–57, doi:10.1109/2.30720. [7] Carlos Hernández & Jorge A. Baier (2011): Real-Time Heuristic Search with Depression Avoidance. In Toby Walsh, editor: IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, IJCAI/AAAI, pp. 578–583, doi:10.5591/978-1-57735-516- 8/IJCAI11-104. [8] Mohd Javaid, Abid Haleem, Ravi Pratap Singh & Rajiv Suman (2021): Substantial capabilities of robotics in enhancing industry 4.0 implementation. Cognitive Robotics 1, pp. 58–75, doi:10.1016/j.cogr.2021.06.001. [9] Sven Koenig (2001): Agent-Centered Search. AI Mag. 22(4), pp. 109–132, doi:10.1609/aimag.v22i4.1596. [10] Sven Koenig (2004): A Comparison of Fast Search Methods for Real-Time Situated Agents, pp. 864–871. doi:10.1109/AAMAS.2004.10122. Available at https://doi.ieeecomputersociety.org/10.1109/ AAMAS.2004.10122. [11] Sven Koenig & Maxim Likhachev (2002): D*Lite, pp. 476–483. Available at http://www.aaai.org/ Library/AAAI/2002/aaai02-072.php. [12] Sven Koenig & Maxim Likhachev (2006): Real-time adaptive A*. In Hideyuki Nakashima, Michael P. Wellman, Gerhard Weiss & Peter Stone, editors: 5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006), Hakodate, Japan, May 8-12, 2006, ACM, pp. 281–288, doi:10.1145/1160633.1160682. [13] Sven Koenig & Xiaoxun Sun (2009): Comparing real-time and incremental heuristic search for real-time situated agents. Auton. Agents Multi Agent Syst. 18(3), pp. 313–341, doi:10.1007/s10458 008-9061-x. [14] Richard E Korf (1990): Real-time heuristic search. Artificial intelligence 42(2-3), pp. 189–211, doi:10.1016/0004-3702(90)90054-4. [15] Maxim Likhachev, Geoffrey J. Gordon & Sebastian Thrun (2003): ARA*: Anytime A* with Provable Bounds on Sub-Optimality, pp. 767–774. Available at https://proceedings.neurips.cc/paper/2003/hash/ ee8fe9093fbbb687bef15a38facc44d2-Abstract.html. [16] Manuel Müller, Timo Müller, Behrang Ashtari Talkhestani, Philipp Marks, Nasser Jazdi & Michael Weyrich (2021): Industrial autonomous systems: a survey on definitions, characteristics and abilities. atAutomatisierungstechnik 69(1), pp. 3–13, doi:10.1515/auto-2020-0131. [17] Michal Pechoucek, Simon G Thompson & Holger Voos (2008): Defence Industry Applications of Autonomous Agents and Multi-Agent Systems. Springer, doi:10.1007/978-3-7643-8571-2. [18] Francisco J Perez-Grau, J Ramiro Martinez-de Dios, Julio L Paneque, J Joaquin Acevedo, Arturo Torres-González, Antidio Viguria, Juan R Astorga & Anibal Ollero (2021): Introducing autonomous aerial robots in industrial manufacturing. Journal of Manufacturing Systems 60, pp. 312–324, doi:10.1016/j.jmsy.2021.06.008. [19] José Ricardo Sánchez-Ibáñez, Carlos Jesús Pérez-del-Pulgar & Alfonso García-Cerezo (2021): Path Planning for Autonomous Mobile Robots: A Review. Sensors 21(23), p. 7898, doi:10.3390/s21237898. [20] Anthony Stentz (1995): The Focussed D* Algorithm for Real-Time Replanning. In: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI 95, Montréal Québec, Canada, August 20-25 1995, 2 Volumes, Morgan Kaufmann, pp. 1652–1659. Available at http://ijcai.org/ Proceedings/95-2/Papers/082.pdf. [21] Dmitry S. Yershov & Steven M. LaValle (2011): Simplicial Dijkstra and A* algorithms for optimal feedback planning. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2011, San Francisco, CA, USA, September 25-30, 2011, IEEE, pp. 3862–3867, doi:10.1109/IROS.2011.6095032. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Too Long; Didn't Read

Developers: Build Less. Deliver More. [Learn how]	

Future Directions in Heuristic Search

Too Long; Didn't Read

Aiding in the focused exploration of potential solutions.

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Future Directions in Heuristic Search

Too Long; Didn't Read

Aiding in the focused exploration of potential solutions.

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES