State-chain sequential feedback reinforcement learning for path planning of autonomous mobile robots

Xin MA; Ya XU; Guo-qiang SUN; Li-xia DENG; Yi-bin LI

doi:10.1631/jzus.C1200226

Your Location：

Home >

Browse articles >

State-chain sequential feedback reinforcement learning for path planning of autonomous mobile robots

计算机与自动化 | Updated：2022-12-09

- State-chain sequential feedback reinforcement learning for path planning of autonomous mobile robots
- State-chain sequential feedback reinforcement learning for path planning of autonomous mobile robots
- 信息与电子工程前沿（英文） 2013年14卷第3期页码：167-178
- Affiliations：
  
  School of Control Science and Engineering, Shandong University, Jinan 250061, China
- Author bio：
  
  [ "E-mail: maxin@sdu.edu.cn" ]
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos.61075091, 61105100, and 61240052), the Natural Science Foundation of Shandong Province, China (No.ZR2012FM036), and the Independent Innovation Foundation of Shandong University, China (Nos.2011JC011 and 2012JC005)
- DOI：10.1631/jzus.C1200226
  中图分类号： TP242.6
- 收稿：2012-07-19，
  
  修回：2013-;1-;4，
  
  纸质出版：2013-03
- Accepted：
Scan QR Code
State-chain sequential feedback reinforcement learning for path planning of autonomous mobile robots[J]. 信息与电子工程前沿（英文）, 2013,14(3):167-178.

Xin MA, Ya XU, Guo-qiang SUN, et al. State-chain sequential feedback reinforcement learning for path planning of autonomous mobile robots[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(3): 167-178.
State-chain sequential feedback reinforcement learning for path planning of autonomous mobile robots[J]. 信息与电子工程前沿（英文）, 2013,14(3):167-178. DOI： 10.1631/jzus.C1200226.

Xin MA, Ya XU, Guo-qiang SUN, et al. State-chain sequential feedback reinforcement learning for path planning of autonomous mobile robots[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(3): 167-178. DOI： 10.1631/jzus.C1200226.

摘要

Abstract

This paper deals with a new approach based on

-learning for solving the problem of mobile robot path planning in complex unknown static environments. As a computational approach to learning through interaction with the environment

reinforcement learning algorithms have been widely used for intelligent robot control

especially in the field of autonomous mobile robots. However

the learning process is slow and cumbersome. For practical applications

rapid rates of convergence are required. Aiming at the problem of slow convergence and long learning time for

-learning based mobile robot path planning

a state-chain sequential feedback

-learning algorithm is proposed for quickly searching for the optimal path of mobile robots in complex unknown static environments. The state chain is built during the searching process. After one action is chosen and the reward is received

the

-values of the state-action pairs on the previously built state chain are sequentially updated with one-step

-learning. With the increasing number of

-values updated after one action

the number of actual steps for convergence decreases and thus

the learning time decreases

where a step is a state transition. Extensive simulations validate the efficiency of the newly proposed approach for mobile robot path planning in complex environments. The results show that the new approach has a high convergence speed and that the robot can find the collision-free optimal path in complex unknown static environments with much shorter time

compared with the one-step

-learning algorithm and the

(λ)-learning algorithm.

关键词

Keywords

references

J. Agirrebeitia , , , R. Aviles , , , I.F. de Bustos , , , G. Ajuria . . A new APF strategy for path planning in environments with obstacles . . Mech. Mach. Theory , , 2005 . . 40 ( ( 6 ): ): 645 - - 658 . . DOI: 10.1016/j.mechmachtheory.2005.01.006 http://doi.org/10.1016/j.mechmachtheory.2005.01.006 . .

C. Alexopoulos , , , P.M. Griffin . . Path planning for a mobile robot . . IEEE Trans. Syst. Man Cybern. , , 1992 . . 22 ( ( 2 ): ): 318 - - 322 . . DOI: 10.1109/21.148404 http://doi.org/10.1109/21.148404 . .

I. Al-Taharwa , , , A. Sheta , , , M. Al-Weshah . . A mobile robot path planning using genetic algorithm in static environment . . J. Comput. Sci. , , 2008 . . 4 ( ( 4 ): ): 341 - - 344 . . . .

J. Barraquand , , , B. Langlois , , , J.C. Latombe . . Numerical potential field techniques for robot path planning . . IEEE Trans. Syst. Man Cybern. , , 1992 . . 22 ( ( 2 ): ): 224 - - 241 . . DOI: 10.1109/21.148426 http://doi.org/10.1109/21.148426 . .

Q. Cao , , , Y. Huang , , , J. Zhou . . An Evolutionary Artificial Potential Field Algorithm for Dynamic Path Planning of Mobile Robot . . Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems , , 2006 . . p.3331 - - 3336 . . DOI: 10.1109/IROS.2006.282508 http://doi.org/10.1109/IROS.2006.282508 . .

O. Castillo , , , L. Trujillo , , , P. Melin . . Multiple objective genetic algorithms for path-planning optimization in autonomous mobile robots . . Soft Comput. , , 2007 . . 11 ( ( 3 ): ): 269 - - 279 . . DOI: 10.1007/s00500-006-0068-4 http://doi.org/10.1007/s00500-006-0068-4 . .

R. Dearden , , , N. Friedman , , , S. Russell . . Bayesian Q-Learning . . Proc. National Conf. on Artificial Intelligence , , 1998 . . p.761 - - 768 . . . .

D. Dolgov , , , S. Thrun , , , M. Montemerlo , , , J. Diebel . . Path planning for autonomous vehicles in unknown semi-structured environments . . Int. J. Robot. Res. , , 2010 . . 29 ( ( 5 ): ): 485 - - 501 . . DOI: 10.1177/0278364909359210 http://doi.org/10.1177/0278364909359210 . .

K. Framling . . Guiding exploration by pre-existing knowledge without modifying reward . . Neur. Networks , , 2007 . . 20 ( ( 6 ): ): 736 - - 747 . . DOI: 10.1016/j.neunet.2007.02.001 http://doi.org/10.1016/j.neunet.2007.02.001 . .

M.A. Garcia , , , O. Montiel , , , O. Castillo , , , R. Sepulveda , , , P. Melin . . Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation . . Appl. Soft Comput. , , 2009 . . 9 ( ( 3 ): ): 1102 - - 1110 . . DOI: 10.1016/j.asoc.2009.02.014 http://doi.org/10.1016/j.asoc.2009.02.014 . .

S.S. Ge , , , Y.J. Cui . . Dynamic motion planning for mobile robots using potential field method . . Auton. Robots , , 2002 . . 13 ( ( 3 ): ): 207 - - 222 . . DOI: 10.1023/A:1020564024509 http://doi.org/10.1023/A:1020564024509 . .

M. Ghatee , , , A. Mohades . . Motion planning in order to optimize the length and clearance applying a hopfield neural network . . Expert Syst. Appl. , , 2009 . . 36 ( ( 3 ): ): 4688 - - 4695 . . DOI: 10.1016/j.eswa.2008.06.040 http://doi.org/10.1016/j.eswa.2008.06.040 . .

D. Gong , , , L. Lu , , , M. Li . . Robot Path Planning in Uncertain Environments Based on Particle Swarm Optimization . . Proc. IEEE Congress on Evolutionary Computation , , 2009 . . p.127 - - 2134 . . DOI: 10.1109/CEC.2009.4983204 http://doi.org/10.1109/CEC.2009.4983204 . .

M. Guo , , , Y. Liu , , , J. Malec . . A new Q-learning algorithm based on the metropolis criterion . . IEEE Trans. Syst. Man Cybern. B , , 2004 . . 34 ( ( 5 ): ): 2140 - - 2143 . . DOI: 10.1109/TSMCB.2004.832154 http://doi.org/10.1109/TSMCB.2004.832154 . .

O. Hachour . . The proposed fuzzy logic navigation approach of autonomous mobile robots in unknown environments . . Int. J. Math. Models Methods Appl. Sci. , , 2009 . . 3 ( ( 3 ): ): 204 - - 218 . . . .

T. Hamagami , , , H. Hirata . . An Adjustment Method of the Number of States of Q-Learning Segmenting State Space Adaptively . . Proc. IEEE Int. Conf. on Systems, Man and Cybernetics , , 2003 . . 4 3062 - - 3067 . . DOI: 10.1109/ICSMC.2003.1244360 http://doi.org/10.1109/ICSMC.2003.1244360 . .

P.E. Hart , , , N.J. Nilsson , , , B. Raphael . . A formal basis for the heuristic determination of minimum cost paths . . IEEE Trans. Syst. Sci. Cybern. , , 1968 . . 4 ( ( 2 ): ): 100 - - 107 . . DOI: 10.1109/TSSC.1968.300136 http://doi.org/10.1109/TSSC.1968.300136 . .

H.J. Hwang , , , H.H. Viet , , , T. Chung . . Q(λ) based vector direction for path planning problem of autonomous mobile robots . . Lect. Notes Electr. Eng. , , 2011 . . 107 ( ( Part 4 ): ): 433 - - 442 . . DOI: 10.1007/978-94-007-2598-0_46 http://doi.org/10.1007/978-94-007-2598-0_46 . .

M.A.K. Jaradat , , , M. Al-Rousan , , , L. Quadan . . Reinforcement based mobile robot navigation in dynamic environment . . Robot. Comput.-Integr. Manuf. , , 2011 . . 27 ( ( 1 ): ): 135 - - 149 . . DOI: 10.1016/j.rcim.2010.06.019 http://doi.org/10.1016/j.rcim.2010.06.019 . .

Z. Jin , , , W. Liu , , , J. Jin . . Partitioning the State Space by Critical States . . Proc. 4th Int. Conf. on Bio-Inspired Computing , , 2009 . . p.1 - - 7 . . DOI: 10.1109/BICTA.2009.5338123 http://doi.org/10.1109/BICTA.2009.5338123 . .

R. Kala , , , A. Shukla , , , R. Tiwari . . Fusion of probabilistic A* algorithm and fuzzy inference system for robotic path planning . . Artif. Intell. Rev. , , 2010 . . 33 ( ( 4 ): ): 307 - - 327 . . DOI: 10.1007/s10462-010-9157-y http://doi.org/10.1007/s10462-010-9157-y . .

S. Koenig , , , R.G. Simmons . . The effect of representation and knowledge on goal-directed exploration with reinforcement-learning algorithms . . Mach. Learn. , , 1996 . . 22 ( ( 1-3 ): ): 227 - - 250 . . DOI: 10.1007/BF00114729 http://doi.org/10.1007/BF00114729 . .

A. Lampton , , , J. Valasek . . Multiresolution State-Space Discretization Method for Q-Learning . . Proc. American Control Conf. , , 2009 . . p.1646 - - 1651 . . DOI: 10.1109/ACC.2009.5160474 http://doi.org/10.1109/ACC.2009.5160474 . .

J.C. Latombe . . Robot Motion Planning . . Kluwer Academic Publishers. , , 1991 . . DOI: 10.1007/978-1-4615-4022-9 http://doi.org/10.1007/978-1-4615-4022-9 . .

C.H. Oh , , , T. Nakashima , , , H. Ishibuchi . . Initialization of Q-Values by Fuzzy Rules for Accelerating QLearning . . Proc. IEEE World Congress on Computational Intelligence and IEEE Int. Joint Conf. on Neural Networks , , 1998 . . 3 2051 - - 2056 . . DOI: 10.1109/IJCNN.1998.687175 http://doi.org/10.1109/IJCNN.1998.687175 . .

J. Peng , , , R.J. Williams . . Incremental multi-step Qlearning . . Mach. Learn. , , 1996 . . 22 ( ( 1-3 ): ): 283 - - 290 . . DOI: 10.1023/A:1018076709321 http://doi.org/10.1023/A:1018076709321 . .

A. Poty , , , P. Melchior , , , A. Oustaloup . . Dynamic Path Planning for Mobile Robots Using Fractional Potential Field . . Proc. 1st Int. Symp. on Control, Communications and Signal Processing , , 2004 . . p.557 - - 561 . . DOI: 10.1109/ISCCSP.2004.1296443 http://doi.org/10.1109/ISCCSP.2004.1296443 . .

Y. Saab , , , M. VanPutte . . Shortest path planning on topographical maps . . IEEE Trans. Syst. Man Cybern. A , , 1999 . . 29 ( ( 1 ): ): 139 - - 150 . . DOI: 10.1109/3468.736370 http://doi.org/10.1109/3468.736370 . .

K. Senda , , , S. Mano , , , S. Fujii . . A Reinforcement Learning Accelerated by State Space Reduction . . SICE Annual Conf. , , 2003 . . 2 1992 - - 1997 . . . .

Y. Song , , , Y. Li , , , C. Li , , , G. Zhang . . An efficient initialization approach of Q-learning for mobile robots . . Int. J. Control Autom. Syst. , , 2012 . . 10 ( ( 1 ): ): 166 - - 172 . . DOI: 10.1007/s12555-012-0119-9 http://doi.org/10.1007/s12555-012-0119-9 . .

S. Still , , , D. Precup . . An information-theoretic approach to curiosity-driven reinforcement learning . . Theory Biosci. , , 2012 . . 131 ( ( 3 ): ): 139 - - 148 . . DOI: 10.1007/s12064-011-0142-z http://doi.org/10.1007/s12064-011-0142-z . .

R.S. Sutton , , , A.G. Barto . . Reinforcement Learning: an Introduction , , : : Cambriage, MA. MIT Press , , 1998 . . .

C.C. Tsai , , , H.C. Huang , , , C.K. Chan . . Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation . . IEEE Trans. Ind. Electron. , , 2011 . . 58 ( ( 10 ): ): 4813 - - 4821 . . DOI: 10.1109/TIE.2011.2109332 http://doi.org/10.1109/TIE.2011.2109332 . .

Z. Wang , , , X. Zhu , , , Q. Han . . Mobile robot path planning based on parameter optimization ant colony algorithm . . Proc. Eng. , , 2011 . . 15 2738 - - 2741 . . DOI: 10.1016/j.proeng.2011.08.515 http://doi.org/10.1016/j.proeng.2011.08.515 . .

C.J.C.H. Watkins . . Learning from Delayed Rewards , , : : Cambridge, UK. University of Cambridge , , 1989 . . .

C.J.C.H. Watkins , , , P. Dayan . . Q-learning . . Mach. Learn. , , 1992 . . 8 ( ( 3-4 ): ): 279 - - 292 . . . .

E. Wiewiora . . Potential-based shaping and Q-value initialization are equivalent . . Artif. Intell. Res. , , 2003 . . 19 205 - - 208 . . . .

S.X. Yang , , , M. Meng . . An efficient neural network approach to dynamic robot motion planning . . Neur. Networks , , 2000 . . 13 ( ( 2 ): ): 143 - - 148 . . DOI: 10.1016/S0893-6080(99)00103-3 http://doi.org/10.1016/S0893-6080(99)00103-3 . .

X. Yang , , , M. Moallem , , , R.V. Patel . . A layered goal-oriented fuzzy motion planning strategy for mobile robot navigation . . IEEE Trans. Syst. Man Cybern. B , , 2005 . . 35 ( ( 6 ): ): 1214 - - 1224 . . DOI: 10.1109/TSMCB.2005.850177 http://doi.org/10.1109/TSMCB.2005.850177 . .

S.C. Yun , , , V. Ganapathy , , , L.O. Chong . . Improved Genetic Algorithms Based Optimum Path Planning for Mobile Robot . . Proc. 11th Int. Conf. on Control, Automation, Robotics and Vision , , 2010 . . p.1565 - - 1570 . . DOI: 10.1109/ICARCV.2010.5707781 http://doi.org/10.1109/ICARCV.2010.5707781 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据