We present a simple algorithm to check for path non-existence for a low-degree-of-freedom (DOF) robot among static obstacles. Our algorithm is based on approximate cell decomposition of configuration space or C-space. We use C-obstacle cell query to check whether a cell lies entirely inside the C-obstacle region. This reduces the path non-existence problem to checking whether a path exists through the set of all cells that do not lie entirely inside the C-obstacle region. We present a simple and efficient algorithm to perform C-obstacle cell query using generalized penetration depth computation. Our algorithm is simple to implement and we demonstrate its performance on three-DOF and four-DOF robots.
Amato, N., Bayazit, O., Dale, L., Jones, C. and Vallejo, D. (1998). OBPRM: an obstacle-based PRM for 3D workspaces . Proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 197- 204.
2.
Avnaim, F. and Boissonnat, J.-D. (1989). Practical exact motion planning of a class of robots with three degrees of freedom. Proceedings of the Canadian Conference on Computational Geometry , p. 19.
3.
Bañon, J. (1990). Implementation and extension of the ladder algorithm . Proceedings IEEE International Conference on Robotics and Automation, pp. 1548-1553.
4.
Barbehenn, M. and Hutchinson, S. (1995). Efficient search and hierarchical motion planning by dynamically maintaining single-source shortest paths trees. IEEE Transactions on Robotics and Automation, 11(2): 198-214.
5.
Basch, J., Guibas, L.J., Hsu, D. and Nguyen, A.T. (2001). Disconnection proofs for motion planning. Proceedings IEEE International Conference on Robotics and Automation .
6.
Brooks, R.A. and Lozano-Pérez, T. (1985). A subdivision algorithm in configuration space for findpath with rotation. IEEE Transactions on Systems, Man, and Cybernetics, 15: 224-233.
7.
Cameron, S. (1997). Enhancing GJK: computing minimum and penetration distance between convex polyhedra. Proceedings IEEE International Conference on Robotics and Automation, pp. 3112-3117.
8.
Canny, J. (1988). The Complexity of Robot Motion Planning. Cambrdige, MA, MIT Press.
9.
Cheng, C.P.P. (2005). Sampling-based motion planning with differential constraints. Ph.D. Thesis, University of Illinois, Urbana-Champaign.
10.
Choset, H., Lynch, K., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. and Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementations. Cambridge, MA, MIT Press.
11.
Donald, B.R. (1984). Motion planning with six degrees of freedom. Technical Report AI-TR-791, MITArtificial Intelligence Lab.
12.
Halperin, D. (2002). Robust geometric computing in motion. The International Journal of Robotics Research, 21(3): 219-232.
13.
Hsu, D., Latombe, J. and Kurniawati, H. (2006). On the probabilistic foundations of probabilistic roadmap planning. The International Journal of Robotics Research , 25(7): 627- 643.
14.
Kavraki, L., Svestka, P., Latombe, J.C. and Overmars, M. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation , 12(4): 566-580.
15.
Kedem, K. and Sharir, M. (1988). An automatic motion planning system for a convex polygonal mobile robot in 2-D polygonal space. Proceedings of the ACM Symposium on Computational Geometry, pp. 329-340.
16.
Kim, Y.J., Lin, M.C. and Manocha, D. (2002). DEEP: an incremental algorithm for penetration depth computation between convex polytopes. Proceedings IEEE Conference on Robotics and Automation, pp. 921-926.
17.
Kuffner, J. and LaValle, S. (2000). RRT-connect: an efficient approach to single-query path planning. Proceedings IEEE International Conference on Robotics and Automation.
18.
Latombe, J. (1991). Robot Motion Planning. Dordrecht , Kluwer.
Lozano-Pérez, T. (1983). Spatial planning: a configuration space approach . IEEE Transactions on Computers, 32: 108-120.
21.
Lozano-Pérez, T. and Wesley, M. (1979). An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM, 22(10): 560-570.
22.
Paden, B., Mess, A. and Fisher, M. (1989). Path planning using a jacobian-based freespace generation algorithm. Proceedings IEEE International Conference on Robotics and Automation.
23.
Pisula, C., Hoff, K., Lin, M. and Manocha, D. (2000). Randomized path planning for a rigid body based on hardware accelerated Voronoi sampling. Proceedings of the 4th International Workshop on Algorithmic Foundations of Robotics.
24.
Schwartz, J.T. and Sharir, M. (1983). On the piano movers probelem II, general techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics, 4: 298-351.
25.
Schwarzer, F., Saha, M. and Latombe, J. (2005). Adaptive dynamic collision checking for single and multiple articulated robots in complex environments. IEEE Transactions on Robotics, 21(3): 338-353.
26.
Simeon, T., Laumond, J.P. and Nissoux, C. (2000). Visibility based probabilistic roadmaps for motion planning. Advanced Robotics Journal, 14(6): 477-493.
27.
van den Bergen, G. (2001). Proximity queries and penetration depth computation on 3D game objects. Proceedings of the Game Developers Conference.
28.
Varadhan, G. and Manocha, D. (2005). Star-shaped roadmaps-a deterministic sampling approach for complete motion planning. Proceedings of Robotics: Science and Systems, Cambridge, MA.
29.
Wise, K.D. and Bowyer, A. (2000). A survey of global configuration-space mapping techniques for a single robot in a static environment. The International Journal of Robotics Research, 19(8): 762-779.
30.
Zhang, L., Kim, Y. and Manocha, D. (2006). A simple path non-existence algorithm using C-obstacle query for low DOF robots. Proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR).
31.
Zhang, L., Kim, Y. and Manocha, D. (2007a). A fast and practical algorithm for generalized penetration depth computation. Proceedings of Robotics: Science and Systems, Atlanta, GA.
32.
Zhang, L., Kim, Y. and Manocha, D. (2007b). A hybrid approach for complete motion planning . Proceedings IEEE/ RSJ International Conference on Intelligent Robots and Systems (IROS), San Diego, CA , pp. 7-14.
33.
Zhang, L., Kim, Y., Varadhan, G. and Manocha, D. (2007c). Generalized penetration depth computation. Computer-Aided Design, 39(8): 625-638.
34.
Zhang, L. and Manocha, D. (2008). A retraction-based RRT planner. Proceedings IEEE International Conference on Robotics and Automation (ICRA), pp. 3743-3750.
35.
Zhu, D. and Latombe, J. (1990). Constraint reformulation in a hierarchical path planner. Proceedings IEEE International Conference on Robotics and Automation, 1918-1923.
36.
Zhu, D. and Latombe, J. (1991). New heuristic algorithms for efficient hierarchical path planning. IEEE Transactions on Robotics and Automation , 7(1): 9-20.
