ISSN 2071-8594

Russian academy of sciences

Editor-in-Chief

Gennady Osipov

K.S. Yakovlev AA-SIPP: any-angle Path Finding Amidst Static and Dynamic Obstacles

Abstract.

A problem of path planning for an agent moving amidst static and dynamic obstacles is considered in the paper as a graph search problem. A novel method to solve it is introduced. The method is based on the combination of two complimentary ideas: any-angle path finding, i.e. augmenting the graph with the edges that connect initially non-adjacent vertices, and safe interval path planning, i.e. grouping the timesteps into the continuous intervals and operating them during heuristic search for a solution. Theoretical and empirical investigation of the algorithm are performed.

Keywords: Path Panning, Path Finding, Heuristic Search, Safe Interval Path Planning, Any-angle Path Planning.

PP. 49-59.

DOI 10.14357/20718594200105

References

1. Lumelsky V., Stepanov A. Dynamic path planning for a mobile automaton with limited information on the environment // IEEE transactions on Automatic control, 31(11), 1986. pp. 1058-1063.
2. McGuire K.N. et al, 2019] McGuire K.N. de Croon G.C.H.E., Tuyls K. A comparative study of bug algorithms for robot navigation // Robotics and Autonomous Systems, 121, 2019. p.103261.
3. Yakovlev K.S., Baskin E.S. Graph Models for Path Planning // Artificial Intelligence and Decision Making, 1, 2013. Pp.5-12.
4. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische mathematik, 1(1), 1959. pp.269-271.
5. Hart P.E., Nilsson N.J. and Raphael B. A formal basis for the heuristic determination of minimum cost paths // IEEE transactions on Systems Science and Cybernetics, 4(2), 1968. pp.100-107.
6. Rufli M., Ferguson, D., Siegwart R. Smooth path planning in constrained environments // In 2009 IEEE International Conference on Robotics and Automation (ICRA 2009), 2009. pp. 3780-3785.
7. Silver D. Cooperative Pathfinding // In Proceedings of The First Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE 2005), 2005. pp.117-122.
8. Phillips M., Likhachev M. SIPP: Safe interval path planning for dynamic environments // In Proceedings of The 2011 IEEE International Conference on Robotics and Automation (ICRA 2011), 2011. pp. 5628–5635.
9. Van Den Berg J.P., Overmars M.H. Roadmap-based motion planning in dynamic environments // IEEE Transactions on Robotics, 21(5), 2005. pp.885-897.
10. ter Mors A.W., Witteveen C., Zutt J., Kuipers F.A. Context-Aware Route Planning // In Proceedings of The 8th German Conference on Multi Agent Systems Technologies (MATES 2010), 2010. pp. 138-149.
11. Nash A., Daniel K., Koenig S., Felner A. Theta*: Anyangle path planning on grids // In Proceedings of The 22nd AAAI Conference on Artificial Intelligence (AAAI 2007), 2007. pp. 1177–1183.
12. Wu X. An efficient antialiasing technique // In Proceedings of The 18th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH-1991), 1991. pp. 143–152.