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.
Visibility graph definition
Definition
The visibility graph is a weighted graph that includes
all paths consisting of line segments between obstacle
vertices, the start, or the goal.
- One node for each polygon vertex.
- Two extra nodes for $x_I$ and $x_G$.
- Between each pair of nodes that can be connected with an obstacle-free segment.
- Weights equal to the distance between nodes.
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 |