Research on Constructing an Approximate Topological Graph and its Path Planning

Abstract:

This paper proposes a new method to construct an approximate Topological Graph based on the traditional constructing voronoi diagram by discrete grids, which combines the PRM (Probabilistic Roadmap Method) path planning thought. By means of the approximate topological graph and the hierarchical thought, the efficiency of path planning is improved. Meanwhile, this method can reduce the unnecessary collision detection and can be effectively used in the path planning of mechanical produce. In the end, this method is analyzed and evaluated, and meanwhile some improvements and simulations about this method are given.

• Periodical: Applied Mechanics and Materials (Volumes 44-47)
• Pages: 596-604
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.44-47.596
• Online since: December 2010
• Authors: Kang Jia, Jun Hong, Yun Long Li, Zong Bin Li
• Keywords: Approximate Topological Graph, Assembly Path Planning, Hierarchical Path Planning

References

[1] Steven M. LaValle. Rapidly-Exploring Random Trees: A New Tool for Path Planning[R]. Dept of Computer Science, lowa State University, (1998).

[2] Lydia E. Kavraki, Petr Svestka, Jean-Claude Latombe and Mark H. Overmars. Probabilistic Roadmaps for Path Planning in High-Dimensional Configuratiion Space[J]. IEEE Transaction on Robotics and Automation (1996), pp.566-580.

DOI: 10.1109/70.508439

[3] Valerie Boor, Mark H. Overmars, A. Frank van der Stappen. Guassian sampling for Probabilistic Roadmap Planners[J]. IEEE Int. Conf. Robot. Auto. (ICRA), 1999, 2: 1018-1023. IEEE Int. Conf. Robot. Auto. (ICRA), Vol. 2(1999), pp.1018-1023.

DOI: 10.1109/robot.1999.772447

[4] Samuel Rodriguez, Shawna Thomas, Roger Pearce, Nancy M. Amato. RESAMPLE: A Region-Sensitive Adaptive Motion Planner. Springer Berlin/Heidelberg, Springer Tracts in Advanced Robotics (2008), pp.285-300.

DOI: 10.1007/978-3-540-68405-3_18

[5] Steven A. Wilarth Nancy M. Amato and Peter F. Stiller. MAPRM: A Probalistic Roadmap Planner with Sampling on the Medial Axis of the Free Space. IEEE Int. Conf. Robot. Auto. (ICRA), 1999, 2: 1024-1031[J]. IEEE Int. Conf. Robot. Autom. (ICRA), Vol. 2(1999).

DOI: 10.1109/robot.1999.772448

[6] Jur P. van den Berg, Mark H. Overmars. Using workspace information as a guide to non-uniform sampling in probabilistic roadmap planners[R]. Information and computer Science, utrecht university, (2003).

DOI: 10.1109/robot.2004.1307191

[7] Gildardo Sanchez and Jean Claude Latombe. A Single-Query Bi-Directional Probabistic Roadmap Planner with Lazy Collision Checking[A]. Robotics Research: The Tenth Int. Symp, R.A. Jarvis and A. Zelinsky (eds. ), Springer Tracts in Advanced Robotics, Springer, (2003).

DOI: 10.1007/3-540-36460-9_27

[8] Etienne Ferre and Jean Paul Laumand. An Iterative Diffusion Alogorithm for part Disassembly[J]. IEEE International Conference on Robotics and Automation, 21, New Orleans LA, USA, (2004).

[9] Yoshifumi KITAMURA, Takaaki TANAKA, Fumio KISHINO and Masahiko YACHIDA. 3-D Path Planning in a Dynamic Environment Using an Octree and an Artificial Potential Field[A]. IROS95 II[C]. Pillsburgh, USA, (1995).

DOI: 10.1109/iros.1995.526259

[10] Klaas Klasing, Dik Wollherr and Martin Buss. Cell-based Probabilistic RoadMaps(CPRM) for Efficient Path Planning in Large Environments[C]. In Proceedings of the 2007 International Conference on Advance Robot (ICAR), Jeju Island, Korea, (2007).

[11] Li Chengming，Chen Jun. The Voronoi diagram generate grid algorithm. Journal of WuHan Technology University of Surveying. (1998), pp.208-210.

[12] Cao Qingjie. The Crystal Growth of Voronoi Diagrams with Obstacles[D]. He Bei Normal University, (2004).

[13] Zou Xiaobin，Cai Zixing. Senor Information-based environment unsmooth modeling and path planning [J]Progress in Natural Science, (2002), pp.1188-1192.

[14] Wang Xinsheng，Liu Jiyuan，Zhuang Dafang，Wu Hehai and Jiang Youhua. New Raste-Based Method for Constructing Voronoi Diagrams. Journal of China University of Mining & Technology, Vol. 32(2005), pp.293-296.