Paper Contribution from Hugh Jack for the IRIR-Precarn conference in Vancouver
1.0 Neural Networks for Robot Motion Planning and Control
Time is an important consideration in planning robot motions. However, in most cases the problem of finding a time optimal robot motion involves an indeterminate solution. Thus, in spite of years of diligent research the motion planners have tended to fall into three categories.
Figure 1.1 - Robot used as test case for this work
Unfortunately, as the motion approaches the optimum, there is an increase in computation time, and the dependance upon mathematical techniques.
There are generally three main problems in motion planning.
(i) Determining and optimal Path.
(ii) Determining an optimal Trajectory
(iii) Determining an optimal Path and Trajectory combination (i.e., an optimal motion plan)
Many authors have proposed excellent solutions to all of these problems. For example, the configuration space method of Lozano-Perez [1983] and the Generalized Cones method of Brooks [1983] can find geometrically good paths, using the shortest path length to approximate shortest time. On the other hand Bobrow et al. [1983] propose a method for finding the time optimal trajectory plan for a given path. Although none of this work addresses the problem of finding the optimal motion.
An optimal motion is a compromise between the best trajectories and paths. Thus, optimal motions are often approached with some form of optimization technique. An example of this is Buchal et al [1989] who represented a motion as a set of points in space and time. They directly optimize the points for minimum time while avoiding collisions, joint torque limits, and joint angle limits.
Previously, optimization methods failed on the basis of excessive computation time and complexity. These features have prevented optimal motion planners from being more than just an academic curiosities.
It was recognized that neural networks may overcome the problems with optimal motion planners. This is not to say that they will replace motion planning methods, but will serve to enhance them. The features which make neural networks particularly attractive are,
• They are fault tolerant (loss of neurons will not stop the computer)
• Their operation speed is very high because of the parallel architecture
• They can learn an approximate model for a problem without construction of a formal model (learning requires a few good examples of inputs and expected outputs)
• Neural Networks can generalize to solutions never learned.
We have found that neural networks have been able to work in real-time to produce good estimates of the optimal motions.
The basic procedure used in this research [Jack, 1991] has been,
1. Find a large number of optimal motions for the robot.
2. Choose some examples from the motion.
3. Train the network to estimate optimal motions.
4. Test the neural network performance against a set of motions not used to train the neural network.
1.2 Finding Optimal Robot Motions:
A new approach was used for finding optimal robot motions. This approach used Bezier spline segments to model the motion, and optimization techniques to reduce the motion time.
The spline was set up to represent the joint positions at various path times. The spline was set up to represent various joint positions at various path times. The optimization routines adjusted the spline points to adjust the path shape. The optimization algorithms adjusted the segment durations to alter the trajectories along the path.
The optimization routines used were a Hookes and Jeeves search [Siddall, 1982] and a Random Walk search. The Hookes and Jeeves search is a pattern search algorithm which searches rapidly, but experiences difficulties in highly constrained problems, like the motion planning problem. The Random Walk search tends to overcome constraints, but converges slowly. Thus, both searches were used repeatedly to move toward the global optimum.
The results for optimizing a number of unique robot motions about the workspace may be seen later in figure 1.3. The reader should note that the results from the optimization are not necessarily located at the global optimum. But, this was considered irrelevant because the neural network was being evaluated for its ability to estimate the solution to be produced by an optimization routine.
After 100 unique motions had been found with the optimization routines, points were randomly chosen from all of the motions. These points were made up of,
• joint angles to goal positions, and,
These were used to train the neural network, for operation as seen in figure 1.2.
The training of the neural network took a few days on a Sun-4 computer. The neural network was feed forward using sigmoidal activation functions, and the backpropagation learning algorithm. There were 20 neurons used in a single hidden layer.
When training was complete, the network was tested using the same points used for testing the optimization routines. The test cases were a different set of motions, not used in the training data. The final results are seen in figure 1.3. The reader should also note that the outputs of the neural network were scaled to their maximum torque limits, unless they were near zero. These results also appear in figure 1.3.
Figure 1.2 - A Neural Network Based Optimal Motion Planner
The reader will note (in figure 1.3) that the scaled outputs of the neural network yielded very good results. In many cases the path times were within 10% of the optimized path time. There were two notable cases. In Case #1, the neural network was able to produce a motion time better than the optimization routines (thus indicating an optimization problem). The results in Case #5 were very poor. A brief summary of conclusions (with no explanation) which appear in Jack [1991] appear below.
(i) The network solution degrades near the edge of the workspace training regions.
(ii) Longer motions allowed errors to accumulate, thus reducing quality.
(iii) The neural network always moved to the goal position, even in the worst cases.
(iv) Poor results from the optimization did not stop the neural network from learning a good estimation.
(v) The neural network software could run faster than any comparable non-linear controller
(vi) The neurons and the network are much simpler than many optimization techniques.
Figure 1.3 - The results for Optimization, and Neural Network test motions.
Bobrow, J.E., Debowsky, S., and Gibson, J.S., 1983, “On the Optimal Control of Robotic Manipulators with Actuator Constraints”, 1983 Proceedings of the American Controls Conference.
Brooks, R.A., 1983, "Planning Collision-free Motions for Pick-and-Place Operations", The International Journal of Robotics Research, Vol. 2, No. 4, pp. 19-44.
Buchal, R.O., and Cherchas, D.B., 1989, “An Iterative Method for Generating Kinematically Feasible Interference-free robot trajectories”, Robotica, Vol.7.
Jack, H., “Application of Neural Networks to Robot Motion Planning and Control”, Masters thesis at the University of Western Ontario, January 1991.
Lozano-Perez, T., 1983, "Spatial Planning: A Configuration Space Approach", IEEE Transactions on Computers, Vol.c-32, No.2.
Siddall, J.N., 1982, “Optimal Engineering Design”, Marcel Dekker Inc., New York.