Graph construction methods

Question 1

Explain how the visibilty graph works to optimize planning

Answer 1

Connect edges of obstructions and walls via lines to find the shortest path

Question 2

What are the cons of the visibility graph?

Answer 2

-Path may make contact with obstruction if bot is not a point mass
-obstructions may need to be inflated

Question 3

Explain how a voroni diagram aims to optimize path planning

Answer 3

Consists of lines that maximise distance from obstructions

Question 4

What are the cons of the voroni diagram?

Answer 4

-weak when there are limited localisation sensors
-planning is not optimal for finding shortest distance
-some paths may be blocked

Question 5

Explain how cell decomposition aims to optimise path planning

Answer 5

At each edge a cell is made and these are either completely free or occupied.
This approach is good for simple obstacles.

Question 6

Cons of cell decomposition

Answer 6

Efficiency is compromised for high density and complex maps