Weighted time-based global hierarchical path planning in dynamic environment
详细信息 查看全文
- 作者：Weiwei Xing (1)
Xiang Wei (1)
Wei Lu (1) - 关键词：path planning ; dynamic environment ; time optimal control ; time cost
- 刊名：Transactions of Tianjin University
- 出版年：2014
- 出版时间：June 2014
- 年：2014
- 卷：20
- 期：3
- 页码：223-231
- 全文大小：
- 参考文献：1. Zhu D Q, Huang H, Yang S X. Dynamic task assignment and path planning of multi-AUV system based on an improved self-organizing map and velocity synthesis method in three-dimensional underwater workspace[J]. / IEEE Transactions on Cybernetics, 2013, 43(2): 504-14.
2. Sud A, Andersen E, Curtis S / et al. Real-time path planning for virtual agents in dynamic environments[C]. In: / ACM SIGGRAPH. Los Angeles, USA, 2008.
3. Guzzi J, Giusti A, Gambardella L M / et al. Human-friendly robot navigation in dynamic environments[C]. In: / IEEE International Conference on Robotics and Automation ( / ICRA). Karlsruhe, Germany, 2013.
4. Garcia M A P, Montiel O, Castillo O / et al. Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation[J]. / Applied Soft Computing, 2009, 9(3): 1102-110. CrossRef
5. Roberge V, Tarbouchi M, Labonte G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J]. / IEEE Transactions on Industrial Informatics, 2013, 9(1): 132-41. CrossRef
6. Koenig S, Likhachev M. Improved fast replanning for robot navigation in unknown terrain[C]. In: / IEEE International Conference on Robotics and Automation ( / ICRA). Washington DC, USA, 2002.
7. Ghaffarkhah A, Mostofi Y. Path planning for networked robotic surveillance[J]. / IEEE Transactions on Signal Processing, 2012, 60(7): 3560-575. CrossRef
8. Yue W Y, Franco J, Cao W W / et al. A new anytime dynamic navigation algorithm[C]. In: / Proceedings of the World Congress on Engineering and Computer Science. San Francisco, USA, 2012.
9. Ergezer H, Leblebicioglu K. Path planning for UAVs for maximum information collection[J]. / IEEE Transactions on Aerospace and Electronic Systems, 2013, 49(1): 502-20. CrossRef
10. Lu Y B, Huo X, Tsiotras P. A beamlet-based graph structure for path planning using multiscale information[J]. / IEEE Transactions on Automatic Control, 2012, 57(5): 1166-178. CrossRef
11. Nirmal B H, Mahendar V, Dilip K P. Time-optimal, collision-free navigation of a car-like mobile robot using neurofuzzy approaches[J]. / Fuzzy Sets and Systems, 2006, 157(16): 2171-204. CrossRef
12. Phillips M, Likhachev M. SIPP: Safe interval path planning for dynamic environments[C]. In: / IEEE International Conference on Robotics and Automation. Shanghai, China, 2011.
13. Ferguson D, Stentz A. The field D* algorithm for improved path planning and replanning in uniform and non-uniform cost environments[R]. Technical Report CMU-TR-RI-05-19. Carnegie Mellon University, USA, 2005.
14. Dijkstra E W. A note on two problems in connexion with graphs[J]. / Numerische Mathematik, 1959, 1(1): 269-71. CrossRef
15. Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths[J]. / IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-07. CrossRef
16. Koenig S, Likhachev M. D* lite[C]. In: / AAAI Conference on Artificial Intelligence. Edmonton, Canada, 2002.
17. Stentz A. The focussed D* algorithm for real-time replanning[C]. In: / International Joint Conference on Artificial Intelligence. Quebec, Canada, 1995.
18. Yue W Y, Franco J, Cao W W / et al. ID* lite: Improved D* lite algorithm[C]. In: / ACM Symposium on Applied Computing. Taiwan, China, 2011.
19. Likhachev M, Ferguson D. Planning long dynamically feasible maneuvers for autonomous vehicles[J]. / The International Journal of Robotics Research, 2009, 28(8): 933-45. CrossRef
20. Rufli M, Ferguson D, Siegwart R. Smooth path planning in constrained environments[C]. In: / IEEE International Conference on Robotics and Automation. Kobe, Japan, 2009.
21. Fox D, Burgard W, Thrun S. The dynamic window approach to collision avoidance[J]. / IEEE Robotics & Automation Magazine, 1997, 4(1): 23-3. CrossRef
22. Wilkie D, van den Berg J, Manocha D. Generalized velocity obstacles[C]. In: / International Conference on Intelligent Robots and Systems. St. Louis, USA, 2009.
23. Abhinav G, Rahul N, Lin M / et al. Hybrid long-range collision avoidance for crowd simulation[C]. In: / ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. Orlando, USA, 2013. - 作者单位：Weiwei Xing (1)
Xiang Wei (1)
Wei Lu (1)
1. School of Software Engineering, Beijing Jiaotong University, Beijing, 100044, China - ISSN：1995-8196
文摘
A weighted time-based global hierarchical path planning method is proposed to obtain the global optimal path from the starting point to the destination with time optimal control. First, the grid- or graph-based modeling is performed and the environment is divided into a set of grids or nodes. Then two time-based features of time interval and time cost are presented. The time intervals for each grid are built, during each interval the condition of the grid remains stable, and a time cost of passing through the grid is defined and assigned to each interval. Furthermore, the weight is introduced for taking both time and distance into consideration, and thus a sequence of multiscale paths with total time cost can be achieved. Experimental results show that the proposed method can handle the complex dynamic environment, obtain the global time optimal path and has the potential to be applied to the autonomous robot navigation and traffic environment.