서론 I.
.
.
.
.
.
,
[1,2,14].
D*
[3].
[4-6].
,
* (Corresponding Author)
: 2011. 2. 20., : 2011. 3. 10., : 2011. 3. 29.
/ /
.
.
. ,
. ,
.
.
.
. ,
. A*
[7].
.
A* .
.
A*
A Path & Velocity Profile Planning Based on A*
Algorithm for Dynamic Environment
, *, ,
(Minhyeok Kwon
1,3, Yeonsik Kang
2, ChangHwan Kim
3, and Gwitae Park
1)
1Korea University
2Kookmin University
3Korea Institute of Science and Technology
Abstract: This paper presents a hierarchical trajectory planning method which can handle a collision-free of the planned path in complex and dynamic environments. A PV (Path & Velocity profile) planning method minimizes a sharp change of orientation and waiting time to avoid a collision with moving obstacle through detour path. The path generation problem is solved by three steps. In the first step, a smooth global path is generated using A* algorithm. The second step sets up the velocity profile for the optimization problem considering the maximum velocity and acceleration. In the third step, the velocity profile for obtaining the shortest path is optimized using the fuzzy and genetic algorithm. To show the validity and effectiveness of the proposed method, realistic simulations are performed.
Keywords: optimal path planning, mobile robot, A* algorithm, obstacle avoidance
Copyright© ICROS 2011
. . II
. III
. IV
.
본론 II.
복잡한 동적 환경 정의 1.
.
,
. 1
.
.
.
.
. 경로 및 속도 프로파일 설계 2.
(PV planning) A*
. D*
A* A*
A* . A*
. A*
.
.
[8].
전역 경로 설계 2.1
A*
. A* (1) [9-11].
(1)
f (n) A* n
.
. g(n) n
euclidean
. h(n) n
.
.
×
(2) h(n)
(2) .
. t(n)
. t(n) . , n
1. .
Fig. 1. A complex and dynamic environment.
2. A*
.
Fig. 2. A Path & Velocity profile (PV) planning based on A*
algorithm for dynamic environment method diagram.
0~1 . d(n) n
Potential Field method Gradient
method [12].
속도 프로파일 최대화 2.2
1
. 3
. a(n), v(n)
s(n), dt(n) ,
(3), (4), (5) , ,
.
(3)
(4)
× (5)
·
4 . 2 ·
. ·
.
.
· x
. ·
. 4
.
.
, x
.
퍼지를 이용한 속도 프로파일 최적화 2.3
2
[8]. 3
. 1 , 2
, 3 .
1 , ,
‘ .’, ‘
.’, ‘
.’ .
2 1 IF-THEN
Fuzzy reasoning Mandani
5, 6 . 5
IF_THEN 1,2 min composition
.
3. .
Fig. 3. The process of calculation for the velocity and arrival time.
안전 지역 충돌 위험 지역
충돌 지역
4. · .
Fig. 4. The maximized Time-Distance Graph.
1. IF-THEN .
Table 1. Fuzzy IF-THEN Rule.
5. Mandani .
Fig. 5. Mandani Fuzzy model - Min composition.
6 5 (Unoin) .
2
Centroid defuzzification
. Centroid defuzzification 7
(6) .
W , a , Z .
(6)
3
. 5 Mandani 9
. 9 ,
1,2 , ,
3,4 ,
5 ,
6,7,8,9 .
9 40
. 20 uniform crossover
.
.
3 .
시뮬레이션 결과 III.
. HOTPP -
A*
[7].
MATLAB
10 , 10
.
8
. A*
.
c-space [13].
8
.
9, 10 - . 9
HOTPP , 10 A*
. ·
6. .
Fig. 6. Inference result of fuzzy.
7. .
Fig. 7. COA (Centroid of Area) result of fuzzy model.
w = 2
w = 3
8. A* .
Fig. 8. A path by the traditional A* algorithm with the heuristic
costs of the collision stability in the nodes.
. HOTPP 9
. 10
.
11, 12 - . HOTPP
. PV planning
. , 11, 12 11
12
.
. MATLAB
HOTPP 0.69 , PV planning 0.98
0.29 c
. 13
, 1,2
.
. ,
HOTPP
9. HOTPP · .
Fig. 9. The Time-Distance graph with a HOTP method.
T-D GRAPH (PV planning)
10. PV planning · .
Fig. 10. The Time-Distance graph with a Path & Velocity profile (PV) planning.
11. HOTPP · .
Fig. 11. The Time-Velocity graph with a HOTP method.
T-D GRAPH (PV planning)
12. PV planning · .
Fig. 12. The Time-Velocity graph with a Path & Velocity profile
(PV) planning.
. PV planning
.
13 PV planning
14 .
- 15 .
.
15. PV planning · .
Fig. 15. The Time-Distance graph with a Path & Velocity profile (PV) planning.
결론 및 향후 계획 IV.
A*
.
.
.
.
참고문헌
[1] Jur P. van den Berg and M. H. Obermars, “Roadmap- based motion planning in dynamic environments,” IEEE, Transactions on Systems, man and Cybernetics, vol. 21, no. 5, pp. 885-897, Oct. 2005.
[2] B. Damas and J. Sntos-Victor, “Avoiding moving ob- stacles: the forbidden velocity map,” IEEE, RSJ Int.
Conf. on Intelligent Robots and Systems, pp. 4393-4398, Oct. 2009.
[3] S. Koenig and M. Likhachev, “Fast replanning for navi- gation in unknown terrain,” IEEE, Transactions on Robotics and Automation, vol. 21, no. 3, pp. 354-363, June 2005.
[4] O. Dahl and L. Nielsen, “Torqe-limited path following by on-line trajectory time scaling,” IEEE, Transactions on Robotics and Automation, vol. 6, pp. 554-561, Oct.
1990.
[5] B. H. Lee, and C. S. G. Lee, “Collision-free motion
12
도착지
출발지
