We present a framework for analyzing and computing motion plans for a robot that operates in an environment that both varies over time and is not completely predictable. We first classify sources of motion-planning uncertainty into four cat egories, and argue that the problems addressed in this article belong to a fundamental category that has received little atten tion. We treat the changing environment in a flexible manner by combining traditional configuration-space concepts with a Markov process that models the environment. For this context, we then propose the use of a motion strategy, which provides a motion command for the robot for each contingency that it might confront. We allow the specification of a desired per formance criterion, such as time or distance, and determine a motion strategy that is optimal with respect to that criterion. We demonstrate the breadth of our framework by applying it to a variety of motion-planning problems. Examples are com puted for problems that involve a changing configuration space, hazardous regions and shelters, and processing of random ser vice requests. To achieve this, we have exploited the powerful principle of optimality, which leads to a dynamic programming- based algorithm for determining optimal strategies. In addition, we present several extensions to the basic framework that incorporate additional concerns, such as sensing issues or changes in the geometry of the robot.
Get full access to this article
View all access options for this article.
References
1.
Barraquand, J., and Ferbach, P.1994. A penalty function method for constrained motion planning . In Proceedings of the IEEE International Conference on Robotics and Automation, IEEE, pp. 1235-1242.
2.
Barraquand, J., Langlois, B., and Latombe, J.C.1992. Numerical potential field techniques for robot path planning . IEEE Trans. Sys. Man Cybernet.22(2):224-241.
3.
Başar, T., and Olsder, G.J.1982. Dynamic Noncooperative Game Theory. London: Academic.
4.
Basye, K., Dean, T., Kirman, J., and Lejter, M.1992. A decision-theoretic approach to planning, perception, and control. IEEE Expert7(4):58-65.
Brost, R.C., and Christiansen, A.D.1993. Probabilistic analysis of manipulation tasks: a research agenda. In Proceedings of the IEEE International Conference on Robotics and Automation, vol. 3. IEEE, pp. 549-556.
7.
Burdick, J.W.1988. Kinematic analysis and design of redundant manipulators. PhD Thesis, Stanford University.
8.
Canny, J.F.1989. On computability of fine motion plans. In Proceedings of the IEEE International Conference on Robotics and Automation, pp. 177-182.
9.
Canny, J. and Reif, J.1987. New lower bound techniques for robot motion planning problems . In Proceedings of the IEEE Conference on Foundations of Computer Science. IEEE, pp. 49-60.
10.
Chang, S.-C., and Liao, D.-T.1994. Scheduling flexible flow shops with no setup effects . IEEE Trans. Robot. Automat.10(2):99-111.
11.
Cutkosky, M.R.1985. Robotic Grasping and Fine Manipulation. Boston, MA: Kluwer Academic.
12.
de Lamadrid, J.G., and Zimmerman, J.1993. Avoidance of obstacles with unknown trajectories: locally optimal paths and path complexity, part I. Robotica11:299-308.
13.
Donald, B.R.1987. Error detection and recovery for robot motion planning with uncertainty. PhD Thesis. Massachusetts Institute of Technology, Cambridge, MA.
14.
Durrant-Whyte, H.F.1988. Uncertain geometry in robotics. IEEE Trans. Robot. Automat.4(1):23-31.
15.
Elfes, A.1989. Using occupancy grids for mobile robot perception and navigation. IEEE Computer22(6):46-57.
16.
Erdmann, M.A.1984. On motion planning with uncertainty. Master's Thesis . Massachusetts Institute of Technology, Cambridge, MA.
17.
Erdmann, M.A.1989. On probabilistic strategies for robot tasks. PhD Thesis . Massachusetts Institute of Technology, Cambridge, MA.
18.
Erdmann, M., and Lozano-Pérez, T.1987. On multiple moving objects . Algorithmica2:477-521.
19.
Firby, R.J.1987. An investigation into reactive planning in complex domains . In Proceedings of the National Conference on Artificial Intelligence.
20.
Fox, A., and Hutchinson, S.1995. Exploiting visual constraints in the synthesis of uncertainty-tolerant motion plans. IEEE Trans. Robot. Automat.1(11):56-71.
21.
Fujimura, K.1992. On motion planning amidst transient obstacles. In Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1488-1493.
22.
Fujimura, K., and Samet, H.1993. Planning a time-minimal motion among moving obstacles . Algorithmica10:41-63.
Hager, G., and Durrant-Whyte, H.G.1988. Information and multi-sensor coordination. In Lemmer, J. F., and Kanal, L. N. (eds), Uncertainty in Artificial Intelligence. New York, NY: Elsevier, pp. 381-393.
27.
Hendler, J.A., and Sanborn, J.C.1987. Planning and reaction in dynamic domains. In Proceedings of the DARPA Workshop on Knowledge-Based Planning Systems.
28.
Hu, H., and Brady, M.1994. A Bayesian approach to real-time obstacle avoidance for a mobile robot. Autonomous Robots1(1):69-92.
29.
Hu, H., Brady, M., and Probert, P.1991. Coping with uncertainty in control and planning for a mobile robot. In IEEE/RSJ International Workshop on Intelligent Robots and Systems. Osaka, Japan, pp. 1025-1030.
Jones, S.T.1980. Solving problems involving variable terrain, part i: a general algorithm. BYTE5(2).
32.
Kant, K., and Zucker, S.W.1986. Toward efficient trajectory planning: the path-velocity decomposition. Int. J. Robot. Res. 5(3):72-89.
33.
Koditschek, D.1989. Robot planning and control via potential functions . In Khatib, O., Craig, J. J., and Lozano-Pérez, T., (eds.), The Robotics Review I. Cambridge, MA: MIT Press.
34.
Kouikoglou, V.S., and Phillis, Y.A.1994. Discrete event modeling and optimization of unreliable production lines with random rates. IEEE Trans. Robot. Automat.10(2):153-159.
Latombe, J.-C., Lazanas, A., and Shekhar, S.1991. Robot motion planning with uncertainty in control and sensing. Art. Intell. 52:1-47.
39.
LaValle, S.M.1995. A game-theoretic framework for robot motion planning. PhD Thesis, University of Illinois, Urbana, IL.
40.
LaValle, S.M., and Hutchinson, S.A.1994. An objective-based stochastic framework for manipulation planning. In Proceedings of the IEEE/RSJ/GI International Conference on Intelligent Robots and Systems , pp. 1772-1779.
41.
LaValle, S.M., and Hutchinson, S.A.1995. A Bayesian segmentation methodology for parametric image models. IEEE Trans. Pattern Analysis Machine Intell.17(2):211-218.
42.
Lin, Z., Zeman, V., and Patel, R.V.1989. On-line robot trajectory planning for catching a moving object. In Proceedings of the IEEE International Conference on Robotics and Automation. IEEE, pp. 1726-1731.
43.
Lozano-Pérez, T., Mason, M.T., and Taylor, R.H.1984. Automatic synthesis of fine-motion strategies for robots . Int. J. Robot. Res. 3(1):3-24.
44.
Lumelsky, V.J., and Stepanov, A.A.1987. Path planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica2:403-430.
45.
Mason, M.T.1982. Compliance and force control for computer controlled manipulators . In Brady, B. et al. (eds.) Robot Motion: Planning and Control, pp. 373-404. Cambridge, MA : MIT Press.
46.
Meng, A.C.1988. Dynamic motion replanning for unexpected obstacles . In Proceedings of the IEEE International Conference on Robotics and Automation. IEEE, pp. 1848-1849.
Miura, J., and Shirai, Y.1991 (Osaka, Japan). Planning of vision and motion for a mobile robot using a probabilistic model of uncertainty In Proceedings of the IEEE/RSJ International Workshop on Intelligent Robots and Systems. pp. 403-408.
Oommen, J.B., Iyengar, S.S., Rao, N.S.V., and Kashyap, R.L.1987. Robot navigation in unknown terrains using learned visibility graphs. Part I: the disjoint convex obstacle case. IEEE J. Robot. Automat.3(6):672-681.
51.
Paul, R.P., and Shimano, B.1976. Compliance and control. In Proceedings of the Joint American Automatic Control Conference, pp. 1694-1699.
52.
Pertin-Troccaz, J.1989. Grasping: a state of the art. In Khatib, O., Craig, J. J. , and Lozano-Pérez, T. (eds), The Robotics Review I. Cambridge, MA: MIT Press.
53.
Rao, N.S.V., Iyengar, S.S., Oommen, J.B., and Kashyap, R.L.1988. On terrain model acquisition by a point robot amidst polyhedral obstacles. IEEE J. Robot. Automat.4:450-455.
54.
Ratering, S., and Gini, M.1993. Robot navigation in a known environment with unknown moving obstacles. In Proceedings of the IEEE International Conference on Robotics and Automation. IEEE, pp. 25-30.
55.
Reif, J.H., and Sharir, M.1985. Motion planning in the presence of moving obstacles . In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE, pp. 144-154.
56.
Rimon, E., and Koditschek, D.E.1992. Exact robot navigation using artificial potential fields. IEEE Trans. Robot. Autom.8(5):501-518.
57.
Rowe, N.C., and Richbourg, R.F.1987. A new method for optimal path planning through nonhomogeneous free space. Technical Report NPS52-87-003, Naval Postgraduate School.
58.
Schmidt, G.K., and Azarm, K.1992. Mobile robot navigation in a dynamic world using an unsteady diffusion equation strategy. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems . IEEE, pp. 642-647.
59.
Schwartz, J.T., and Sharir, M.1988. A survey of motion planning and related geometric algorithms . Art. Intell. 37:157-169.
60.
Sharma, R.1992a. Locally efficient path planning in an uncertain, dynamic environment using a probabilistic model. IEEE Trans. Robot. Automat. 8(1):105-110.
61.
Sharma, R.1992b. A probabilistic framework for dynamic motion planning in partially known environments. In Proceedings of the 1992 IEEE International Conference on Robotics and Automation. IEEE, pp. 2459-2464.
62.
Sharma, R., LaValle, S.M., and Hutchinson, S.A.1996. Optimizing robot motion strategies for assembly with stochastic models of the assembly process. IEEE Trans. Robot. Automat.12(2):160-174.
63.
Sharma, R., Mount, D.M., and Aloimonos, Y.1993. Probabilistic analysis of some navigation strategies in a dynamic environment. IEEE Trans. Sys. Man. Cybernet. 23(5):1465-1474.
64.
Shih, C.L., Lee, T.-T., and Gruver, W.A.1990. A unified approach for robot motion planning with moving polyhedral obstacles. IEEE Trans. Sys. Man Cybernet . 20:903-915.
65.
Spence, R., and Hutchinson, S.A.1992. Dealing with unexpected moving obstacles by integrating potential field planning with inverse dynamics control . In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, pp. 1485-1490.
66.
Spong, M., and Vidyasagar, I.1989. Robot Dynamics and Control. Wiley.
67.
Stark, H., and Woods, J.W.1986. Probability, Random Processes, and Estimation Theory for Engineers. Englewood Cliffs, NJ: Prentice-Hall.
68.
Stentz, A.1994. Optimal and efficient path planning for partially known environments. In Proceedings of the IEEE International Conference on Robotics and Automation. IEEE , pp. 3310-3317.
69.
Suh, S.-H., and Shin, K.G.1988. A variational dynamic programming approach to robot-path planning with a distance-safety criterion. IEEE Trans. Robot. Automat.4(3):334-349.
70.
Sutner, K., and Maass, W.1988. Motion planning among time dependent obstacles . Acta Informatica26:93-122.
71.
Takeda, H. and Latombe, J.-C.1992 (Nice, France). Sensory uncertainty field for mobile robot navigation. In Proceedings of the IEEE International Conference on Robotics and Automation. IEEE, pp. 2465-2472.
72.
van Delft, C.1994. Approximate solutions for large-scale piecewise deterministic control systems arising in manufacturing flow control models . IEEE Trans. Robot. Automat.10(2):142-152.
73.
Whitney, D.1977. Force feedback control of manipulator fine motions . J. Dyn. Sys. Meas. Control99:91-97.
74.
Wilfong, G.1988. Motion planning in the presence of movable obstacles . In Proceedings of the ACM Symposium on Computational Geometry . pp. 279-288.
75.
Zhu, Q.1991. Hidden Markov model for dynamic obstacle avoidance of mobile robot navigation. IEEE Trans. Robot. Automat.7(3):390-397.
