Hierarchical dynamic programming for robot path planning

被引:15
作者
Bakker, B [1 ]
Zivkovic, Z [1 ]
Kröse, B [1 ]
机构
[1] Univ Amsterdam, Inst Informat, Intelligent Autonomous Syst Grp, NL-1098 SJ Amsterdam, Netherlands
来源
2005 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS, VOLS 1-4 | 2005年
关键词
planning; dynamic programming; hierarchical methods; multiresolution methods; mobile robots;
D O I
10.1109/IROS.2005.1545548
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This paper addresses the question how robot planning (e.g. for navigation) can be done with hierarchical maps. We present an algorithm for hierarchical path planning for stochastic tasks, based on Markov Decision Processes (MDPs) and dynamic programming. It is more efficient than standard dynamic programming for "Flat" MDPs, because it reduces the state space for all levels in its hierarchy and it allows reuse of previously computed partial policies. This computational advantage comes at the cost of some extra memory and overhead to represent and coordinate the hierarchical system, and in some cases somewhat longer paths to target locations. We demonstrate the method on artificially generated MDP data, and on real robot data from our vision-controlled robot navigating in an office environment.
引用
收藏
页码:3720 / 3725
页数:6
相关论文
共 15 条
[1]  
[Anonymous], 2004, PROC C INTELLIGENT A
[2]  
Bertsekas DP, 2012, DYNAMIC PROGRAMMING, V2
[3]  
BUHMANN J, 1995, AI MAG, V16, P31
[4]  
Dayan P., 1993, ADV NEURAL INFORM PR, V5
[5]   Hierarchical reinforcement learning with the MAXQ value function decomposition [J].
Dietterich, TG .
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2000, 13 :227-303
[6]   Improving efficiency in mobile robot task planning through world abstraction [J].
Galindo, C ;
Fernández-Madrigal, JA ;
González, J .
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 2004, 20 (04) :677-690
[7]   MULTIRESOLUTION PATH PLANNING FOR MOBILE ROBOTS [J].
KAMBHAMPATI, S ;
DAVIS, LS .
IEEE JOURNAL OF ROBOTICS AND AUTOMATION, 1986, 2 (03) :135-145
[8]  
KUIPERS BJ, 1977, TR418 MIT ART INT LA
[9]   Distinctive image features from scale-invariant keypoints [J].
Lowe, DG .
INTERNATIONAL JOURNAL OF COMPUTER VISION, 2004, 60 (02) :91-110
[10]  
PETERSON JK, 1991, P ART NEUR NETW ENG, P789