Incremental search algorithms reuse information from previous searches to speed up the current search and solve search problems potentially much faster than solving them repeatedly from scratch. They are widely popular in solving dynamic path-planning problems such as navigation for unmanned ground vehicles and motion planning for articulated robots. For example, existing incremental search algorithms such as D* and D* Lite have been adapted for use with much success in various robotic applications including the Mars rovers and autonomous vehicles in the DARPA Urban Challenge.
Our current research focus is on investigating the applicability of such algorithms in conjunction with answer set programming to solve multi-agent pathfinding problems. Applications of this problem is numerous including the coordination of robots in automated warehouses.
Representative Publications
- Poom Pianpak, Tran Cao Son, Z O. Toups, and William Yeoh. “A Distributed Solver for Multi-Agent Path Finding Problems.” In Proceedings of the International Conference on Distributed Artificial Intelligence (DAI), pages 2:1-2:7, 2019.
- Van Nguyen, Philipp Obermeier, Tran Cao Son, Torsten Schaub, and William Yeoh. “Generalized Target Assignment and Path Finding Using Answer Set Programming.” In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 1216-1223, 2017.
- William Yeoh, Pradeep Varakantham, Xiaoxun Sun, and Sven Koenig. “Incremental DCOP Search Algorithms for Solving Dynamic DCOP Problems.” In Proceedings of the International Conference on Intelligent Agent Technology (IAT), pages 257-263, 2015.
- Ping Hou, William Yeoh, and Tran Cao Son. “Solving Uncertain MDPs by Reusing State Information and Plans.” In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 2285-2292, 2014.