Dynamic Path Method Using Tree Structure

다국어 초록 (Multilingual Abstract)

There are many works in collision avoidance were introduced. But most of previous works are developed for finding a shortest length path or collision free and safest path from start point to goal point. Our proposed approach is focused on how to optimize driving methods on given fixed path depending on speed by getting informations of time and gasoline consumption. For this implementation, all collision positions are estimated based on time calculations first. Then cost function is derived which consists of two partial costs: total time and gasoline consumption for each speed. The total time function is the addition of two times. The first time is time between initial car state and collision area and the second time is time to wait until collision area becomes safe. The gasoline consumption calculates the amount of car fuel consumption until collision area. The tree structure is created depending on number of collisions to find optimum. It solved our problem by minimum sum after adding up all path values from root to leaves.
The result looks like a sequence of actions that leads from initial state to a goal state. The overview of the algorithm and some experimental results are presented.

국문 초록 (Abstract)

최근에는 물체의 이동에 소요되는 비용, 즉 소요시간, 연료 소모량, 이동 거리 및 속도를 최소화하는 알고리즘의 발달로 인해 실세계에서 이동에 대한 최소 비용을 예측 가능하게 하는 연구가 진행 되고 있다. 목적지까지이동하는 하나의 물체는 이동중에 움직이는 또 다른 물체와의 충돌이 발생할 수 있으며 충돌을 피하기 위해 정지하거나 속도를 줄임으로써이동 시간 및 연료 소모량에 비 효율적인 성능(비용)이 발생하게 된다. 물체의 이동에 소요되는 비용(시간+연료소모량)을 최소화하기 위해 이동 속도 및 연료 소모량에 대한 최적의 성능을 찾는알고리즘을 제안한다. 움직이는 다른 물체와의 충돌 위험지역까지 이동하는 구간에 대하여 가능한모든 이동 속도와 연료 소모량, 충돌 회피를 위해 대기하는 시간들의 요소를각각에 대한 가중치 연산을 통해 결과를 도출하고 결과를트리 형태로 구성함으로써 각각의 구간에 소요되는 최소 비용과 누적된 값에 대한 최적의 이동속도와 연료 소모량을 추론해 내는 방법을 제안 함으로써 움직이는 물체의 이동에 대한 효율적인 비용을 보장하고자 한다.

목차 (Table of Contents)

• 1. Introduction 1
• 1.1 Background and Motivation 1
• 1.2 Organization 2
• 2. Related Works 4
• 2.1 Vector Based Approach 4
• 2.2 Curvature Velocity Method and Dynamic Window Approach 6
• 2.3 Bug1 Algorithm 8
• 2.4 Potential Field Method 9
• 3. Proposed Dynamic Path Method 12
• 3.1 Time Calculations and Collision Position 14
• 3.2 Fuel Consumption 16
• 3.3 Cost Function 18
• 3.4 Tree Structure Generation 19
• 3.5 Optimal Path Search 21
• 4. Experiment and Results 24
• 4.1 Comparison of Possible Methods 25
• 5. Conclusion 29
• Reference 31
• ABSTRACT* 33
• 요약문* 35
• Acknowledgement 36