This paper discusses the implementation of a new type of path finding algorithm that is particularly well suited to robots with many degrees of freedom (dof), such as the robotic arm type devices used in welding a car body. In particular, it is ideal constrained environments, and where the robot might have to maneuver through small spaces. Standard heuristic methods for robots with a smaller dof have not expanded very well to many-dof systems, due to the exponentially increasing number of configurations, and the resulting increase in storage space and decrease in speed. A fairly successful planner for many-dof systems is a potential field planner known as the Randomized Path Planner (RPP). However, it does poorly when required to move between areas separated by small spaces (traps), due to the small chances of moving through the space, and is also very slow.
The most important distinction between this and other planners is the use of a preprocessing stage. This is done only once for each environment and then paths between different configurations can be calculated very quickly used the preprocessed data. The preprocessor starts by randomly generating a large number (on the order of a few thousand) of allowable configurations for the robot. Next, the algorithm tries to connect each configuration to a small number of the closest configurations, using a very simple planner. A graph is used to represent the problem, with each node representing a configuration, and the edges representing pairs of nodes that for which a path has been generated. The resulting graph may consist of several disconnected sections, known as components. The third stage of preprocessing is the critical one - the enhancement of the "difficult" areas. Each node is assigned a weight corresponding to its difficulty, as determined by some heuristic. The one used in the paper assigns a higher difficulty to nodes with a lower degree. The algorithm then randomly generates a number of new configurations that are "near" the old nodes. More new nodes are generated for a node with a higher difficulty. The algorithm tries to connect each of these new nodes to its parent node, and to the closest nodes in a different component than its parent. Very small components are discarded, and then RPP is used in a final attempt to connect all of the components. Several close pairs of nodes in different configurations a given to RPP for each pair of components. Ideally, after this there is only one large configuration (or several, if there is no way for the robot to move between certain configurations).
Now the actual path finding is very simple. The algorithm tries to connect the start and end positions to the same configuration (first using the simple planner, and RPP if necessary), and then does a breadth-first search to find the shortest path through the graph.
The test cases in the paper confirmed that most of the time was spent in the preprocessor. There is a fairly linear relationship between the number of nodes generated and the time spent (roughly 0.05 sec/node). Once enough nodes had been generated (about 6000 total - 3000 at first, and 3000 for the enhancement), the time to connect a position to a network settled down to about 0.03 - 0.07 seconds. Further increases did not usually help. If the enhancement step was skipped, and all the nodes generated at first, the preprocessing took roughly 25% longer, and the threshold increased to around 10000 nodes. The number of failures was much higher, but the ones that worked took a similar amount of time to connect a position, demonstrating the importance of the enhancement step to successfully navigating the traps.
Missing from the paper were any comparisons of this algorithm's performance versus others that have been researched. It was implied, but not said, that the others did not even work well enough to talk about, at least for the types of environments tested. The algorithm's one major drawback is the pre-processing time required - which effectively eliminates its usefulness in a dynamic environment. However, it does seem to perform quite well in its intended static environment, producing fast enough responses for real-time control of many applications. The research has very direct applications in industry, filling a gap in path-finding, and should help reduce the time it currently takes to program such complicated robots.