Visibility Graphs
In Chapter 13 we saw how to plan a path for a robot from a given start position to a given goal position. The algorithm we gave always finds a path if it exists, but we made no claims about the quality of the path: it could make a large detour, or make lo
- PDF / 149,959 Bytes
- 11 Pages / 547.087 x 685.984 pts Page_size
- 60 Downloads / 191 Views
Visibility Graphs Finding the Shortest Route
In Chapter 13 we saw how to plan a path for a robot from a given start position to a given goal position. The algorithm we gave always finds a path if it exists, but we made no claims about the quality of the path: it could make a large detour, or make lots of unnecessary turns. In practical situations we would prefer to find not just any path, but a good path.
Figure 15.1 A shortest path
What constitutes a good path depends on the robot. In general, the longer a path, the more time it will take the robot to reach its goal position. For a mobile robot on a factory floor this means it can transport less goods per time unit, resulting in a loss of productivity. Therefore we would prefer a short path. Often there are other issues that play a role as well. For example, some robots can only move in a straight line; they have to slow down, stop, and rotate, before they can start moving into a different direction, so any turn along the path causes some delay. For this type of robot not only the path length but also the number of turns on the path has to be taken into account. In this chapter we ignore this aspect; we only show how to compute the Euclidean shortest path for a translating planar robot.
323
Chapter 15
15.1
Shortest Paths for a Point Robot
VISIBILITY GRAPHS
As in Chapter 13 we first consider the case of a point robot moving among a set S of disjoint simple polygons in the plane. The polygons in S are called obstacles, and their total number of edges is denoted by n. Obstacles are open sets, so the robot is allowed to touch them. We are given a start position pstart and a goal position pgoal , which we assume are in the free space. Our goal is to compute a shortest collision-free path from pstart to pgoal , that is, a shortest path that does not intersect the interior of any of the obstacles. Notice that we cannot say the shortest path, because it need not be unique. For a shortest path to exist, it is important that obstacles are open sets; if they were closed, then (unless the robot can move to its goal in a straight line) a shortest path would not exist, as it would always be possible to shorten a path by moving closer to an obstacle. Let’s quickly review the method from Chapter 13. We computed a trapezoidal map T(Cfree ) of the free configuration space Cfree . For a point robot, Cfree was simply the empty space between the obstacles, so this was rather easy. The key idea was then to replace the continuous work space, where there are infinitely many paths, by a discrete road map Groad , where there are only finitely many paths. The road map we used was a plane graph with nodes in the centers of the trapezoids of T(Cfree ) and in the middle of the vertical extensions that separate adjacent trapezoids. The nodes in the center of each trapezoid were connected to the nodes on its boundary. After finding the trapezoids containing the start and goal position of the robot, we found a path in the road map between the nodes in the centers of these trapezoids by breadth-
Data Loading...
