Page 277 - Introduction to Autonomous Mobile Robots

262

start Chapter 6

goal

Figure 6.2
Visibility graph [21]. The nodes of the graph are the initial and goal points and the vertices of the con-
figuration space obstacles (polygons). All nodes which are visible from each other are connected by
straight-line segments, defining the road map. This means there are also edges along each polygon’s
sides.

Visibility graph. The visibility graph for a polygonal configuration space C consists of
edges joining all pairs of vertices that can see each other (including both the initial and goal
positions as vertices as well). The unobstructed straight lines (roads) joining those vertices
are obviously the shortest distances between them. The task of the path planner is thus to
find the shortest path from the initial position to the goal position along the roads defined
by the visibility graph (figure 6.2).
Visibility graph path planning is moderately popular in mobile robotics, partly because
implementation is quite simple. Particularly when the environmental representation
describes objects in the environment as polygons in either continuous or discrete space, the
visibility graph search can employ the obstacle polygon descriptions readily.
There are, however, two important caveats when employing visibility graph search.
First, the size of the representation and the number of edges and nodes increase with the
number of obstacle polygons. Therefore the method is extremely fast and efficient in sparse
environments, but can be slow and inefficient compared to other techniques when used in
densely populated environments.
The second caveat is a much more serious potential flaw: the solution paths found by
visibility graph planning tend to take the robot as close as possible to obstacles on the way