8. Navigation: Visibility graphs
Introduction
Definition
A visibility graph can be used to compute shortest paths
among known polygonal planar obstacles.
Problem
Given:- A set of obstacles represented as polygons.
- A non-obstacle starting state $x_I$.
- A non-obstacle ending state $x_G$.
- The shortest path between $x_I$ and $x_G$ that avoids the obstacles.
Intuition
Imagine a candidate path as a piece of string connecting the start and goal points. Make that path smaller and smaller by tightening the string. What kinds of paths can we get?Visibility graph definition
Definition
The visibility graph is a weighted graph that includes
all paths consisting of line segments between obstacle
vertices, the start position, or the goal position.
- One node for each polygon vertex.
- Two extra nodes for $x_I$ and $x_G$.
- Edges between each pair of nodes that can be connected with an obstacle-free line segment.
- Edge weights equal to the distance between nodes.
Visibility graph example
After computing the visibility graph, plan a path using your favorite path-finding algorithm for graphs.
Some common mistakes:
- Leaving out edges between adjacent vertices, i.e. along the obstacle boundaries.
- Leaving out edges between non-adjacent vertices on the same obstacle.
Comment 1: Some edges can be eliminated
Consider an edge in the visibility graph between obstacle vertices.- Extend that edge into a full line.
- Inspect one of the endpoints of the edge. Do the two obstacle edges lie on opposite side of the extended line? If so, eliminate that edge.
- Repeat for the other endpoint.
To determine if an edge can be removed, imagine that
it extends just a little further in each direction. If that
extension goes into an obstacle, then the edge is not part of the
reduced visibility graph.Comment 2: Shortest vs. Safest paths
The paths generated by this method are, by construction, very unsafe. Be careful what you ask for! |
 |
| visibility graph | Voronoi graph |