Slides6

Planning and NavigationWhere am I going? How do I get there?: 

Planning and Navigation Where am I going? How do I get there? 6

Configuration Space: 

Configuration Space 6.2.1

Path Planning Overview: 

Path Planning Overview 1. Road Map, Graph construction Identify a set of routes within the free space Where to put the nodes? Topology-based: at distinctive locations Metric-based: where features disappear or get visible 2. Cell decomposition Discriminate between free and occupied cells Where to put the cell boundaries? Topology- and metric-based: where features disappear or get visible 3. Potential Field Imposing a mathematical function over the space 6.2.1

Visibility Graph: 

Visibility Graph 6.2.1

Voronoi Diagram: 

Voronoi Diagram 6.2.1

Voronoi, Sysquake Demo: 

Voronoi, Sysquake Demo 6.2.1

Exact Cell Decomposition: 

Exact Cell Decomposition 6.2.1

Approximate Cell Decomposition: 

Approximate Cell Decomposition 6.2.1

Adaptive Cell Decomposition: 

Adaptive Cell Decomposition 6.2.1

Path / Graph Search Strategies: 

Path / Graph Search Strategies 6.2.1

Potential Field: 

Potential Field 6.2.1

Attractive Potential Field: 

Attractive Potential Field Parabolic function representing the Euclidean distance to the goal Attracting force converges linearly towards 0 6.2.1

Repulsing Potential Field: 

Repulsing Potential Field Barrier around the whole obstacle strong close to the obstacle no influence far from the obstacle : minimum distance to the object Field tends to infinity as q gets closer to the object 6.2.1

Sysquake Demo: 

Sysquake Demo 6.2.1

Extended Potential Field Method: 

Extended Potential Field Method 6.2.1 Khatib and Chatila

Harmonic Potentials: 

Harmonic Potentials 6.2.1

Obstacle Avoidance: 

Obstacle Avoidance known obstacles (map) Planed path observed obstacle v(t), w(t) 6.2.2

Bug Algorithm (Bug1): 

Bug Algorithm (Bug1) 6.2.2

Bug Algorithm (Bug2): 

Bug Algorithm (Bug2) 6.2.2

Vector Field Histogram (VFH): 

Vector Field Histogram (VFH) 6.2.2 Borenstein et al.

Vector Field Histogram + (VFH+): 

Vector Field Histogram + (VFH+) 6.2.2 Borenstein et al.

Video VFH: 

Video VFH Borenstein et al. 6.2.2

Bubble Band Concept: 

Bubble Band Concept 6.2.2 Khatib and Chatila

Basic Curvature Velocity Methods (CVM): 

Basic Curvature Velocity Methods (CVM) Simmons et al. 6.2.2

Dynamic Window Approach: 

Dynamic Window Approach 6.2.2 Fox and Burgard, Brock and Khatib

Global Dynamic Window Approach: 

Global Dynamic Window Approach 6.2.2

Schlegel Approach: 

Schlegel Approach 6.2.2

EPFL-ASL approach: 

EPFL-ASL approach 6.2.2

EPFL-ASL approach: 

EPFL-ASL approach 6.2.2

Comparison of Obstacle Avoidance Algorithms: 

Acrobat Document Comparison of Obstacle Avoidance Algorithms 6.2.2

Comparison of Obstacle Avoidance Algorithms: 

6.2.2 Comparison of Obstacle Avoidance Algorithms

Comparison of Obstacle Avoidance Algorithms: 

6.2.2 Comparison of Obstacle Avoidance Algorithms