Robot motion planning on N-dimensional star worlds among moving obstacles

被引:37
作者
Conn, RA [1 ]
Kam, M
机构
[1] Drexel Univ, Dept Elect & Comp Engn, Philadelphia, PA 19104 USA
[2] Johns Hopkins Univ, Appl Phys Lab, Laurel, MD 20723 USA
来源
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION | 1998年 / 14卷 / 02期
关键词
motion planning; moving obstacles; vector fields;
D O I
10.1109/70.681250
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Inspired by an idea of Rimon and Koditschek [1], we develop a motion planning algorithm for a point robot traveling among moving obstacles in an N-dimensional spare. The navigating point must meet a goal point at a fixed time T, while avoiding several translating, nonrotating, nonintersecting obstacles on its way. All obstacles, the goal point, and the navigating point are confined to the interior of a starshaped set in R-N over the time interval [0, T], Full a priori knowledge of the goal's location and of the obstacle's trajectories is assumed. We observe that the topology of the obstacle-free space is invariant in the time interval [0, T] as long as the obstacles are nonintersecting and as long as they do not cover the goal point at any time during [0, T]. Using this fact we reduce the problem, for any fixed time t(0) is an element of [0, T], to a stationary-obstacle problem, which is then solved using the method of Rimon and Koditschek [1], The fact that the obstacle-free space is topologically invariant allows a solution to the moving-obstacle problem over [0, T] through a continuous deformation of the stationary-obstacle solution obtained at time to. We construct a vector field whose flow is in fact one such deformation. We believe that ours is the first global solution to the moving-obstacle path-planning problem which uses vector fields.
引用
收藏
页码:320 / 325
页数:6
相关论文
共 6 条
[1]  
Canny J., 1987, P 28 ANN IEEE S FDN, P49
[2]  
Fujimura K., 1990, Proceedings 1990 IEEE International Conference on Robotics and Automation (Cat. No.90CH2876-1), P324, DOI 10.1109/ROBOT.1990.125996
[3]  
HWANG YK, 1992, COMPUT SURV, V24, P219, DOI 10.1145/136035.136037
[4]  
Latombe J.-C., 2012, ROBOT MOTION PLANNIN, V124
[5]  
REIF J, 1985, P 26 ANN S FDN COMP, P144
[6]   EXACT ROBOT NAVIGATION USING ARTIFICIAL POTENTIAL FUNCTIONS [J].
RIMON, E ;
KODITSCHEK, DE .
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1992, 8 (05) :501-518