Knowledge-driven path planning for mobile robots: relative state tree

详细信息    查看全文

• 作者：Yang Chen (1)
  Lei Cheng (1)
  Huaiyu Wu (1)
  Xingang Zhao (2)
  Jianda Han (2)
  
  1. School of Information Science and Engineering ; Wuhan University of Science and Technology ; Wuhan聽 ; 430081 ; China
  2. State Key Laboratory of Robotics ; Shenyang Institute of Automation ; Chinese Academy of Sciences ; Shenyang聽 ; 110016 ; China
  
• 关键词：Path planning ; Relative state tree ; Hierarchical tree ; Incremental learning ; Autonomous planning
• 刊名：Soft Computing - A Fusion of Foundations, Methodologies and Applications
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：19
• 期：3
• 页码：763-773
• 全文大小：1,276 KB
• 参考文献：1. Chen C, Li HX, Dong D (2008) Hybrid control for robot navigation: a hierarchical Q-learning algorithm. IEEE Robot Autom Mag 15(2):37鈥?7 CrossRef
  2. Chen M, Wu QX, Jiang CS (2008) A modified ant optimization algorithm for path planning of UCAV. Appl Soft Comput 8(4):1712鈥?718 CrossRef
  3. Chen Y, Han J, Zhao X (2012) Three-dimensional path planning for unmanned aerial vehicle based on linear programming. Robotica 30(5):773鈥?81 3574711000993" target="_blank" title="It opens in new window">CrossRef
  4. Earl MG, D鈥橝ndrea R (2005) Iterative MILP methods for vehicle control problems. IEEE Trans Robot 21(6):1158鈥?167 3499" target="_blank" title="It opens in new window">CrossRef
  5. Fahimi F (2009) Autonomous robots modeling, path planning, and control. Springer Science+Business Media LLC, Boston, USA
  6. Fahimi F, Nataraj C, Ashrafiuon H (2009) Real-time obstacle avoidance for multiple mobile robots[J]. Robotica 27(2):189鈥?98 3574708004438" target="_blank" title="It opens in new window">CrossRef
  7. Hu Y, Yang SX (2004) A knowledge based genetic algorithm for path planning of a mobile robot. In: Proceedings of the 2004 IEEE International Conference on Robotics & Automation, pp 4350鈥?355
  8. Hawkins J, Blakeslee S (2004) On Intelligence. Henry Holt and Company, New York
  9. Hwang JY, Kim JS, Lim SS, Park KH (2003) A fast path planning by path graph optimization [J]. IEEE Trans Syst Man Cybern Part A Syst Hum 33(1):121鈥?29 3.812599" target="_blank" title="It opens in new window">CrossRef
  10. Kim JO, Khosla PK (1992) Real-time obstacle avoidance using harmonic potential functions [J]. IEEE Trans Robot Autom 8(3):338鈥?49 3352" target="_blank" title="It opens in new window">CrossRef
  11. Kuwata Y, How J (2004) Three dimensional receding horizon control for UAVs. In: Proceedings of AIAA Guidance, Navigation, and Control Conference, pp 2100鈥?113
  12. Ladd AM, Kavraki LE (2004) Measure theoretic analysis of probabilistic path planning [J]. IEEE Trans Robot Autom 20(2):229鈥?42 CrossRef
  13. Likhachev M, Ferguson D, Gordon G, Stentz A, Thrun S (2005) Anytime dynamic A*: An anytime, replanning algorithm. In: Proceedings of the International Conference on Automated Planning and Scheduling, pp 262鈥?71
  14. Maarja K (2003) Global level path planning for mobile robots in dynamic environments. J Intell Robot Syst 38(1):55鈥?3 3/A:1026296011183" target="_blank" title="It opens in new window">CrossRef
  15. Ota J, Katsuki R, Mizuta T, Arai T, Ueyama T, Nishiyama T (2003) Smooth path planning by using visibility graph-like method. In: Proceedings IEEE International Conference on Robotics and Automation, pp. 3770鈥?775
  16. Richard SS, Andrew GB (1998) Reinforcement learning: an introduction. The MIT Press, Cambridge
  17. Richards A, How JP (2002) Aircraft trajectory planning with collision avoidance using mixed integer linear programming. In: Proceedings of American Control Conference, pp 1936鈥?941
  18. Sakahara H, Masutani Y, Miyazaki F (2008) Real-time motion planning in unknown environment: A Voronoi-based StRRT (SpatiotemporalRRT). In: The Society of Instrument and Control Engineers Annual Conference, pp 2326鈥?331
  19. Temizer S (2011) Planning under uncertainty for dynamic collision avoidance. Dissertation, Massachusetts Institute of Technology
  20. Vasudevan C, Ganesan K (1996) Case-based path planning for autonomous underwater vehicles. Auton Robot 3(2鈥?):79鈥?9 CrossRef
  21. Venkateswaran N, Prahasaran R (2010) Path planning for space robots: based on knowledge extrapolation and risk factors. In: Proceedings of the 2010 IEEE International Conference on Automation and Logistics, pp 373鈥?78
  22. Weng J, Hwang W (2007) Incremental hierarchical discriminant regression. IEEE Trans Neural Netw 18(2):397鈥?15
  23. Yershova A, LaValle SM (2007) Improving motion-planning algorithms by efficient nearest-neighbor searching. IEEE Trans Robot 23(1):151鈥?57 CrossRef
  24. Zhang D, Zhao X, Chen Y (2011) Application of the case-based learning based on KD-tree in unmanned helicopter. In: 2011 International Conference on Electric and Electronics, pp 721鈥?29
  25. Zu D, Han JD, Tan DL (2006) Acceleration space LP for the path planning of dynamic target pursuit and obstacle avoidance. In: Proceedings of the 6th World Congress on Intelligent Control and Automation, pp 9084鈥?088
  26. Zu D, Han JD, Tan DL (2007) Trajectory generation in relative velocity coordinates using mixed integer linear programming with IHDR guidance. In: The 3rd annual IEEE Conference on Automation Science and Engineering, pp 1125鈥?130
  
• 刊物类别：Engineering
• 刊物主题：Numerical and Computational Methods in Engineering
  Theory of Computation
  Computing Methodologies
  Mathematical Logic and Foundations
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1433-7479

文摘

Path planning is important in the field of mobile robot. However, traditional path planning techniques optimize the navigation path solely based on the models of the robot and the environments. Owing to the time-varying environment, the robot is expected to launch the replanning procedure in real-time continuously. It is slow and wastes computing resources for repeated decisions. In this study, a new perspective is adopted which utilizes a knowledge-driven approach for path planning. The concept of relative state tree is proposed to develop an incremental learning method based on a path planning knowledge base. The knowledge library, which stores a collection of the mappings from environmental information to robot decisions, can be established by offline or online learnings. As the robot plans online, its movement is guided by the optimal decision that is retrieved from the library based on the information which matches mostly the current environment. A large number of simulations are executed to verify the proposed method. When comparing to \(k\) -d tree, this novel method has shown to use smaller storage space and have higher efficiency.