Email this article A Framed-quadtree based on Reversed D* Path Planning Approach for Intelligent Mobile Robot
Abstract
This paper proposes a new path planning system combining framed-quadtree representation with the reversed D* algorithm to improve the efficiency of path planning. The utilization of framed-quadtree representation is for improving the decomposed efficiency of the environment and maintaining the representation capability of maps. And the feature of reversed D* algorithm is that it does not need to calculate the value of the goal distance. The core of reversed D* algorithm is to use the “robot distance” to establish the local potential field, which realizes dynamic optimization by the way of search “escaping point” as the middle goal location. The theoretical analyzing and studying simulation results to the proposed method demonstrate that the proposed path planning system has potential.
Keywords
References
M.K.Habib, S.Yuta, “Development and implementation of navigation system for an autonomous mobile robot working in a building environment with its real time application”, 15th Annual Conference of IEEE Industrial Electronics Society, 1989, pp613-622.
H.Moravec, A.Elfes, “High resolution maps from wide angle sonar”, IEEE International Conference on Robotics and Automation, 1985, pp116- 121.
T. Soon, Mook Jeong, “The Local Minimum Escape using The Grid Map”, IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems, 2008, pp146-151.
http://dx.doi.org/10.1109/MFI.2008.4648095
W.Bingfeng, C.Shigang, “Mobile robot map building based on grid arrangement”, International Conference on Artificial Intelligence and Computational Intelligence, 2009, pp288-291.
P.Ting-Kai, “Path planning approach in unknown environment”, International Journal of Automation and Computing, vol.20, No.7, 2010, pp310-316.
C. Kai, M. Wurm, “Bridging the gap between feature- and grid-based SLAM”, Robotics and Autonomous Systems, vol.58, No.3, 2010, pp310-316.
K.Tae-Bum, S.Jae-Bok, “Thinning-based topological exploration using position probability of topological nodes”, IEEE International Conference on Robotics and Automation, 2006, pp797-802.
L Kyoungmin, K.C.Wan, “Navigable voronoi diagram : a local path planner for mobile robots using sonar sensors”, IEEE/RSJ International Conference on Intelligent Robots and Systems, 2007, pp2813-2818.
Chaoxia Shi, “Online topological map building and qualitative localization in large-scale environment”, Robotics and Autonomous Systems, vol.58, No.7, 2010, pp310-316.
J.L.Blanco, J.A.Fernandez-Madrigal, “A New Approach for Large-Scale Localization and Mapping: Hybrid Metric-Topological SLAM”, IEEE International Conference on Robotics and Automation, 2007, pp2061-2067.
J.L.Blanco, J.A.Fernandez-Madrigal, “Toward a Unified Bayesian Approach to Hybrid Metric--Topological SLAM”, IEEE Transactions on Robotics, vol.2, No.24, 2008, pp259-270.
http://dx.doi.org/10.1109/TRO.2008.918049
D.Fox, W.Burgard, “The dynamic window approach to collision avoidance”, Robotics & Automation Magazine, vol.4, No.1, 1997, pp23-33.
http://dx.doi.org/10.1109/100.580977
O.Brock, O.Khatib, “High-speed navigation using the global dynamic window approach”, IEEE International Conference on Robotics and Automation, 1999, pp 341-346.
H.Berti, A.D.Sappa, “Autonomous robot navigation with a global and asymptotic convergence”, IEEE International Conference on Robotics and Automation, 2007, pp2712-2717.
C.Chih-Chung, L.Feng, “Velocity space approach with region analysis and look-ahead verification for robot navigation”, IEEE Conference on Decision and Control 2009, pp5971-5976.
O.Khatib, “Real-time obstacle avoidance for manipulators and mobile robots”, IEEE International Conference on Robotics and Automation, 1985, pp500- 505.
P.Veelaert, W.Bogaerts, “Ultrasonic potential field sensor for obstacle avoidance”, IEEE Transactions on Robotics and Automation, vol.4, No.15, 1999, pp774-779.
http://dx.doi.org/10.1109/70.782033
S.S.Ge, Y.J.Cui, “New potential functions for mobile robot path planning”, IEEE Transactions on Robotics and Automation, vol.5, No.16, 2000, pp615-620.
http://dx.doi.org/10.1109/70.880813
Y.B.Jun, H.K.Sung, “Path planning of unmanned vehicle using potential field and lane detection”, SICE Annual Conference, 2010, pp1339-1342.
A.A.Masoud, “Managing the Dynamics of a Harmonic Potential Field-Guided Robot in a Cluttered Environment”, IEEE Transactions on Industrial Electronics, vol.2, No.56, 2009, pp488-496.
http://dx.doi.org/10.1109/TIE.2008.2002720
Danny.Z.Chen, Robert J. Szczerba, “A Framed-Quadtree Approach for Determining Euclidean Shortest Paths in a 2-D Environment”, IEEE Transactions On Robotics And Automation, Vol. 13, No. 5, Oct,1997.
KarenI,Trovato, Leo.Dorst, “Differential A*”, IEEE Transactions on Knowledge and data engineering, vol.6, No.14, 2002, pp1218-1229.
S.Koenig, M.Likhachev, “Improved fast replanning for robot navigation in unknown terrain”, IEEE International Conference on Robotics and Automation, 2002, pp968- 975.
D.Cagigas, “Hierarchical D* algorithm with materialization of costs for robot path planning”, Robotics and Autonomous Systems, vol.52, No.14,2005, pp190–208.
http://dx.doi.org/10.1016/j.robot.2005.04.005
D.Likhachev, “Anytime search in dynamic graphs”, Artificial Intelligence, vol.172, No.14, 2008, pp1613–1643.
http://dx.doi.org/10.1016/j.artint.2007.11.009
Z.X. Cai, “The Navigation Theory and Approach for Mobil Robot under Unknown Environment”, Beijing: Science Press, 2009, pp. 333-335. (in Chinese)
J.L.Guzman, M.Berenguel, “An interactive tool for mobile robot motion planning”, Robotics and Autonomous Systems, vol.56, 2008, pp396–409.
http://dx.doi.org/10.1016/j.robot.2007.10.001
Full Text: PDF