Montana Tech THE UNIVERSITY OF MONTANA |
||
|
Research 98 Back to Past Research Activities Page In This Issue In-Depth
Look at Young
Researchers Geologic
Maps Environmental
Research
Activity Chemistry
Building
________________ Student Production Design & Editing Team: |
NASA-Montana Tech Joint Venture: Calculating the Shortest Path for a Robot to Follow in Space Keith B. Olson, Ph.D. Since 1994, Montana Tech has been funded by the NASA-University Joint Venture (JOVE) program. This program provides start-up funds for Colleges and Universities that historically received minimal funding from the space agency. The program supports collaborations between college researchers and one of NASA’s established research centers. Dr. Keith Olson, Professor of Computer Science, is collaborating with the NASA-Ames Research Center at Moffat Field, California to determine the shortest path for a robot to follow in space. The following scenario expresses the problem. Consider a free-flying robot with a camera making an inspection tour of a space facility such as the International Space Station. One possible approach is to fly the robot to an inspection point, stop it, then turn it to proceed toward the next inspection point. This approach is a waste of resources. However, flying the robot at a constant speed and turning it as it approaches a given point, so it continues on to the next point without stopping, consumes significantly less fuel. This scenario requires a path with more gentle curves than the sudden turns that occur if the vehicle is allowed to stop. Consider a certain minimum curvature to the path and then seek the shortest path between two successive positions. This problem does not concern itself with the shortest or most efficient path for a spacecraft to follow between Earth and Mars. There is concern here with problems of a local nature—problems where gravity and other influences can be considered as constants. A position implies more than a location. Position also implies the orientation of the robot at a given location. When a position is considered, we must recognize that it does no good for the robot to arrive at an inspection point if its camera is pointing in the wrong direction. The problem is to determine the most efficient path from one position to another in order to plan an inspection tour for the robot.
In 1957, L. E. Dubins1 solved this problem for a robot moving in two-dimensional space, such as on a factory floor. Dubins established that minimal paths of this type always consist of straight-line segments (denoted by the symbol L) and circular segments (denoted by C) whose radius cannot be smaller than the structure of the robot. These shortest paths always consist of a circular segment, a linear segment, and another circular segment if the initial and final positions are sufficiently far apart. In other cases, the shortest path may consist of three circular segments. For adequately separated initial and final positions, there are four possible circular-linear-circular (CLC) paths. An example is shown in figure 1. One of these paths will always be the shortest feasible path from one position to the other. Figure 2 shows an example of an initial-terminal position pair where the shortest path is circular-circular-circular (CCC).
Figure 2. The shortest path
between
Instead of a robot working on a factory floor, consider a robot in space. If the line connecting the initial and final positions and the vectors defining the orientation of the robot at those positions are all coplanar, then the solution given by Dubins applies to this three-dimensional problem. Our group is concerned with a scenario where locations and vectors are not coplanar. The problem was solved by determining that the proper generalization of the circle used by Dubins is a torus. We used a torus that is generated by rotating the circle tangent to the position vector around that position vector (see figure 3). The line defined by the vector and the central point of the torus is known as the axis of the torus. From this point, we intrepret “sufficiently far apart” to mean that the axis of each torus does not intersect the interior of the other torus. With this torus construction, we can solve the problem provided the initial and final positions are sufficiently far apart. If a torus of this type is constructed around both the initial and final positions, there will be a line through each axis that is also tangent to each torus. A CLC path is constructed from the initial position to the final position by moving along the first torus to its point of contact with the line, moving along the line to its point of contact with the second torus, and concluding with a circular path along the second torus to the final position (see figure 4). In space there are four possible paths, just as there are four possible paths in the two-dimensional case. One of these paths always represents the shortest and most efficient path between the initial and final positions. Note that figure 4 shows only one such path; in the case illustrated, it is the shortest possible path. Many problems remain to be solved. In the case of positions that are relatively close together, the simple analogue of moving from circles to torii does not appear to work. Various proposed solutions have been examined, but the robot is always required to make a sharper turn than its structure allows. The presence of obstacles must also be considered, including the object being inspected, since it may lie across the direct path considered by this algorithm. A more involved problem is to find a path that uses the least energy rather than just finding the shortest physical path. This path would be significant if it required less energy to move the robot in one direction than in another. Ultimately, this is the sort of path we would like to find; shortest is only best if it uses limited resources efficiently. The solution to this problem may be found by working in configuration space, where three coordinates are possible for the location of the robot and two or three more coordinates define its orientation. These axes would have scales that correspond to the cost of movement in each direction. The shortest path in this space would then correspond to the cheapest path in real space. Finding this solution would require extending the present solution from three dimensions to five or six—certainly difficult for three-dimensional humans to visualize! Figure 3. The torus constructed around a robot position in three-dimensional space. The robot is located at the center of the torus, and the arrow indicates the direction the robot is facing. The arrow also defines the axis of the torus.
Figure 4. A CLC path between the initial and final positions of a robot in three-dimensional space. Only the shortest path between these two positions is represented.
|
|
[../../#] |
