Avoiding Moving Obstacles by Deviation from a Mobile Robot’s Nominal Path

Abstract

This paper deals with the problem of obstacle avoidance by deviation from the nominal path. Deviation is the only option available to the robot when the acceleration or deceleration plan on the nominal path fails to produce a viable avoidance strategy. The obstacle avoidance on the nominal path was dealt with in our previous development, where the robot’s motion was only subject to an upper bound on its speed. When the robot has to deviate, its motion is subject to a maximum steering constraint and a maximum deviation constraint in addition to the maximum speed constraint. The problem is solved geometrically by identifying final states for the robot that are reachable, satisfy all the constraints, and guarantee collision avoidance. The final state-reachability conditions that we obtain in the process ensure that no unnecessary deviation plan is initiated. These conditions, along with the simplicity of the geometric arguments we employ, make our scheme an attractive option for on-line implementation. The only significant complexity arises when minimizing the performance index. We have suggested dynamic programming as an optimization tool, but any other nonlinear optimization technique can be adopted.

Get full access to this article

View all access options for this article.

References

Alexander, J. C., and Maddocks, J. H. 1989. On the kinematics of wheeled mobile robots . Intl. J. Robot. Res. 8(5): 15–27 .

Bazaraa, M. S., Sherali, H. D., and Shetty, C. M. 1993. Non-linear Programming. New York: John Wiley .

Bell, D. S. 1993. Mathematics of Linear and Nonlinear Systems. Oxford, UK: Oxford University Press .

Borenstein, J., and Koren, Y. 1991. The vector field histogram—fast obstacle avoidance for mobile robots . IEEE Trans. Robot. Automat. 7: 278–288 .

Boudarel, R., Delmas, J., and Guichet, P. 1971. Dynamic Programming and Its Applications to Optimal Control. Academic Press .

Bryson, A. E., and Ho, Y.-C. 1975. Applied Optimal Control. Hemisphere .

Hu, H., Brady, M., and Probert, P. 1991 (Brighton, UK, December). Navigation and control of a mobile robot among moving obstacles . Proc. of the 30th Intl. Conf. on Decision and Control, pp. 698–703 .

Kant, K., and Zucker, S. 1988 (April). Planning collision-free trajectories in time-varying environments: A two-level hierarchy. Proc. of the IEEE Intl. Conf. on Robot. and Automat. Los Alamitos, CA: IEEE , pp. 1644–1649.

Khatib, O. 1986. Real-time obstacle avoidance for manipulators and mobile robots . Intl. J. Robot. Res. 5(1): 90–98 .

10.

Kyriakopoulos, K., and Saridis, G. 1993. An integrated collision prediction and avoidance scheme for mobile robots in nonstationary environments . Automatica 29(2): 309–322 .

11.

Luenberger, D. G. 1979. Introduction to Dynamic Systems. New York: John Wiley .

12.

Muir, P. F., and Neuman, C. P. 1987. Kinematic modeling of wheeled mobile robots . J. Robot. Sys. 4(2): 281–340 .

13.

Murray, R. M., Li, Z., and Sastry, S. S. 1993. A Mathematical Introduction to Robotic Manipulation. Boca Raton, FL: CRC Press .

14.

Papageorgiou, M., and Steinkogler, A. 1994. Real-time optimal control of moving vehicles on changing environments . IEEE Trans. Control Sys. Tech. 2(4): 447–454 .

15.

Tsoularis, A. 1997. Collision avoidance in unstructured environments. PhD thesis, Department of Cybernetics, University of Reading.

16.

Tsoularis, A., and Kambhampati, C. 1998. On-line planning for collision avoidance on the nominal path . J. Intell. Robot. Sys. 21(4): 327–371 .