A new robot navigation algorithm for dynamic unknown environments based on dynamic path re-computation and an improved scout ant algorithm

被引:54
作者
Zhu, Qingbao [1 ,2 ]
Hu, Jun [1 ,2 ]
Cai, Wenbin [1 ,2 ]
Henschen, Larry [3 ]
机构
[1] Nanjing Normal Univ, Sch Comp Sci, Nanjing 210097, Peoples R China
[2] Jiangsu Res Ctr Informat Secur & Confidential Eng, Nanjing 210097, Peoples R China
[3] Northwestern Univ, Evanston, IL 60208 USA
基金
中国国家自然科学基金;
关键词
Unknown dynamic environment; Robot navigation; Scout ant; Path planning; SYSTEM;
D O I
10.1016/j.asoc.2011.07.016
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
A difficult issue in robot navigation or path planning in an unknown environment with static or dynamic obstacles is to find a globally optimal path from the start to the target point and at the same time avoid collisions. We present a novel and effective robot navigation algorithm for dynamic unknown environments based on an improved ant-based algorithm. In our approach two bidirectional groups of scout ants cooperate with each other to find a local optimal static navigation path within the visual domain of the robot. The robot then predicts the collision points with moving objects, and the scout ants find a new collision-free local navigation path. This process is carried out dynamically after each step of the robot, thereby allowing the robot to adjust its path as new obstacles come into view or existing obstacles move in new directions. Therefore, the robot can not only avoid collision but also make its paths globally optimal or near-optimal by making a series of dynamic adjustments to locally optimal paths. The simulation results have shown that the algorithm has good effect, high real-time performance, and is very suitable for real-time navigation in complex and dynamic environments. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码:4667 / 4676
页数:10
相关论文
共 31 条
[1]   Line of sight robot navigation toward a moving goal [J].
Belkhouche, Fethi ;
Belkhouche, Boumediene ;
Rastgoufard, Parviz .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 2006, 36 (02) :255-267
[2]  
Bin N, 2004, IEEE SYS MAN CYBERN, P735
[3]   Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks [J].
Chabini, I ;
Lan, S .
IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, 2002, 3 (01) :60-74
[4]   Hybrid control for robot navigation - A hierarchical Q-learning algorithm [J].
Chen, Chunlin ;
Li, Han-Xiong ;
Dong, Daoyi .
IEEE ROBOTICS & AUTOMATION MAGAZINE, 2008, 15 (02) :37-47
[5]  
Dorigo M., 1997, IEEE Transactions on Evolutionary Computation, V1, P53, DOI 10.1109/4235.585892
[6]  
Dorigo M., 1999, Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), P1470, DOI 10.1109/CEC.1999.782657
[7]   A hybrid approach for mobile robot path planning in dynamic environments [J].
Du, Zhenjun ;
Qu, Daokui ;
Xu, Fang ;
Xu, Dianguo .
2007 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND BIOMIMETICS, VOLS 1-5, 2007, :1058-+
[8]  
Fan XP, 2003, 2003 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS, INTELLIGENT SYSTEMS AND SIGNAL PROCESSING, VOLS 1 AND 2, PROCEEDINGS, P131
[9]   Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation [J].
Garcia, M. A. Porta ;
Montiel, Oscar ;
Castillo, Oscar ;
Sepulveda, Roberto ;
Melin, Patricia .
APPLIED SOFT COMPUTING, 2009, 9 (03) :1102-1110
[10]  
Garro B.A., 2006, 4 C EL ROB AUT MECH, P444