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

Computer & Automation | 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
- Frontiers of Information Technology & Electronic Engineering Vol. 14, Issue 3, Pages: 167-178(2013)
- Affiliations：
  
  School of Control Science and Engineering, Shandong University, Jinan 250061, China
- Author bio：
  
  [ "E-mail: maxin@sdu.edu.cn" ]
- Funds：
- DOI：10.1631/jzus.C1200226
  CLC： TP242.6
- Received：19 July 2012，
  
  Revised：2013-;1-;4，
  
  Published：2013-03
- Accepted：
Scan QR Code
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：

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 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

Weiwei Zhao╖‡

Peng Li

Zhenzhen Hu

Dawei Feng

Shaofei Chen

Jiaxing Chen

Weilin Yuan╖

Zhen Wang

Related Institution

Laboratory for Parallel and Distributed Processing of National University of Defense Technology

College of Control Science and Engineering of National University of Defense Technology

College of Information and Communication of National University of Defense Technology

The College of Computer, National University of Defense Technology (NUDT)

Intelligent Game and Decision Lab (IGDL), Defense Innovation Institute

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰