Planning High-quality Paths and Corridors Amidst Obstacles

Abstract

The motion-planning problem, involving the computation of a collision-free path for a moving entity amidst obstacles, is a central problem in fields such robotics and game design. In this paper we study the problem of planning high-quality paths. A high-quality path should have some desirable properties: it should be short, avoiding long detours, and at the same time it should stay at a safe distance from the obstacles, namely it should have clearance. We suggest a quality measure for paths, which balances between the above criteria of minimizing the path length while maximizing its clearance. We analyze the properties of optimal paths according to our measure, and devise an approximation algorithm to compute near-optimal paths amidst polygonal obstacles in the plane. We also apply our quality measure to corridors. Instead of planning a one-dimensional motion path for a moving entity, it is often more convenient to let the entity move in a corridor, where the exact motion path is determined by a local planner. We show that planning an optimal corridor is equivalent to planning an optimal path with bounded clearance.

Keywords

Motion planning bi-criteria optimization corridors

Get full access to this article

View all access options for this article.

References

Agarwal, P.K. , van Kreveld, M. and Overmars, M. (1993). Intersection queries in curved objects. Journal of Algorithms, 15(2): 229-266.

Choset, H. , Lynch, K.M. , Hutchinson, S. , Kantor, G. , Burgard, W. , Kavraki, L.E. and Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementations. Boston, MA, MIT Press.

Gelfand, I.M. and Fomin, S.V. (2000). Calculus of Variations. New York, Dover.

Gray, A. (1997). Logarithmic spirals. Modern Differential Geometry of Curves and Surfaces with Mathematica, 2nd edn. CRC Press, Boca Raton, FL, pp. 40-42.

Kamphuis, A. and Overmars, M.H. (2004). Motion planning for coherent groups of entities . Proceedings of the IEEE International Conference Robotics and Automation (ICRA), pp.3815-3822.

Kamphuis, A. , Pettre, J. , Overmars, M.H. and Laumond, J.-P. (2005). Path finding for the animation of walking characters . Proceedings of Eurographics/ACM SIGGRAPH Symposium on Computer Animation, pp. 8-9.

Kavraki, L.E. , Svestka, P. , Latombe, J.-C. and Overmars, M.H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation , 12: 566-580.

Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The International Journal on Robotics Research , 5(1): 90-98.

Latombe, J.-C. (1991). Robot Motion Planning. Boston, MA, Kluwer Academic.

10.

Lee, D.-T. and Drysdale, R.L. III (1981). Generalization of Voronoi diagrams in the plane. SIAM Journal on Computing, 10(1): 73-87.

11.

Mitchell, J.S.B. and Papadimitriou, C.H. (1991). The weighted region problem: Finding shortest paths through a weighted planar subdivision. Journal of the ACM, 38(1): 18-73.

12.

Mitchell, J.S.B. and Polishchuk, V. (2007). Thick non-crossing paths and minimum-cost flows in polygonal domains. Proceedings of the 23rd Symposium on Computational Geometry (SCG), pp. 56-65.

13.

Mitchell, J.S.B. (2004). Shortest paths and networks. Handbook of Discrete and Computational Geometry, 2nd edn, Goodman, J. E. and O'Rourke, J. (eds). London, Chapman & Hall/CRC, pp. 607-642.

14.

Nieuwenhuisen, D. and Overmars, M.H. (2004). Motion planning for camera movements. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 3870-3876.

15.

Nieuwenhuisen, D. and Overmars, M.H. (2004). Useful cycles in probabilistic roadmap graphs . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 446-452.

16.

Nieuwenhuisen, D. , Kamphuis, A. , Mooijekind, M. and Overmars, M.H. (2004). Automatic construction of roadmaps for path planning in games. Proceedings of the International Conference on Computer Games: Artificial Intelligence, Design and Education, pp. 285-292.

17.

' Dunlaing, C. and Yap, C.K. (1985). A "retraction" method for planning the motion of a disk. Journal of Algorithms, 6: 104-111.

18.

Overmars, M.H. (2005). Path planning for games. Proceedings of the 3rd International Game Design and Technology Workshop (GDTW 2005), pp. 29-33.

19.

Pocchiola, M. and Vegter, G. (1996). The visibility complex. International Journal of Computational Geometry and Applications, 6(3): 279-308.

20.

Reif, J. and Wang, H. (1995). Social potential fields: a distributed behavioral control for autonomous robots. Proceedings of the International Workshop on Algorithmic Foundations of Robotics (WAFR), Goldberg, K., Halperin, D. , Latombe, J.-C. and Wilson, R. (eds). Wellesley, MA, A. K. Peters, pp. 431-459.

21.

Rimon, E. and Koditschek, D.E. (1992). Exact robot navigation using artificial potential fields. IEEE Transactions on Robotics and Automation, 8: 501-518.

22.

Russel, S. and Norvig, P. (2002). Artificial Intelligence: A Modern Approach, 2nd edn. Englewood Cliffs, NJ, Prentice Hall.

23.

Sharir, M. (2004). Algorithmic motion planning. Handbook of Discrete and Computational Geometry, 2nd edn, Goodman, J. E. and O'Rourke, J. (eds). London, Chapman & Hall/CRC, pp. 1037-1064.

24.

Song, G. , Miller, S. and Amato, N.M. (2001). Customizing PRM roadmaps at query time. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 1500-1505.

25.

Wein, R. , van den Berg, J.P. and Halperin, D. 2007. The visibility-Voronoi complex and its applications. Computational Geometry: Theory and Applications, 36(1): 66-87.