Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-24T02:00:51.610Z Has data issue: false hasContentIssue false
  • English
  • Français

Avoidance of obstacles with unknown trajectories: locally optimal paths and path complexity, Part I

Published online by Cambridge University Press:  09 March 2009

James Gil de Lamadrid  and
Jill Zimmerman†
Get access Rights & Permissions [Opens in a new window]

Summary

We consider the problem of moving a point robot through a two dimensional workspace containing polygonal obstacles moving on unknown trajectories. We propose to use sensor information to predict the trajectories of the obstacles, and interleave path planning and execution. In this paper, we present preliminary work in which we propose our basic algorithm and define a locally minimum velocity path as an optimal robot trajectory, given only local information about obstacle trajectories. In the sequel (part II) to this paper we will show that the complexity of a path planning problem can be characterized by how frequently the robot must change directions to approximate the locally minimum velocity path.

Keywords

Obstacle avoidanceUnknown trajectoriesPoint robotSensor information
Type
Research Article
Information
Robotica , Volume 11 , Issue 4 , July 1993 , pp. 299 - 308
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Lozano-Perez, T., Mason, M.T. and Taylor, R.H., “Automatic Synthesis of Fine-Motion Strategies for Robots”, Int. J. Robotics Research, 3, No. 1, 3–24 (Spring, 1984).CrossRefGoogle Scholar
2.Lozano-Perez, T. and Wesley, M.A., “An Algorithm for Planning Collision Free Paths among Polyhedral Ob- stacles” Communications of the ACM 22, No. 10, 560–570 (10, 1979).CrossRefGoogle Scholar
3.Schwartz, J.T. and Sharir, M., “On the Piano Movers' Problem: I. The Special Case of a Rigid Polygonal Body moving amidst Polygonal Barriers” Advances in Applied Mathematics 36, 345–398 (1983).Google Scholar
4.Schwartz, J.T., and Sharir, M., “On the Piano Movers' Problem: III. Coordinating the Motion of Several Independent Bodies: The Special Case of Circular Bodies Moving Amidst Polygonal Barriers” Int. J. Robotics Research 2, No. 3, 46–75 (Fall, 1983).CrossRefGoogle Scholar
5.Oommen, B.J. and Reichstein, I., “On the Problem of Translating an Elliptic Object Through a Workspace of Elliptic Obstacles” Robotica 5, Part 3, pp. 187–196, (1987).CrossRefGoogle Scholar
6.Maddila, S.R., “Decomposition Algorithm for Moving a Ladder Among Rectangular Obstacles” IEEE Interna- tional Conference on Robotics and Automation, (1986) pp. 1413–1418.Google Scholar
7.Avnaim, F., Boissonnat, J.D. and Faverjon, B., “A Practical Exact Motion Planning Algorithm for Polygonal Objects Amidst Polygonal Obstacles” IEEE International Conference on Robotics and Automation, Philadelphia, (04, 1988) pp. 1656–1661.Google Scholar
8.Schwartz, J.T., Hopcroft, J. and Sharir, M., Planning, Geometry and Complexity of Robot Motion (Ablex Pub. Co., Norwood, NJ., 1987) pp. 267–281.Google Scholar
9.Sharir, M. and Sifrony, S., Coordinated Motion Planning for Two Independent Robots (New York University, Dept. of Computer Science, Tech Report No. 360, 04 1988).CrossRefGoogle Scholar
10.Yap, C.K., “Algorithmic Motion Planning” In: Algorithmic and Geometric Aspects of Robotics (Schwartz, J.T., and Yap, C.K., eds.). (Lawrence Erlbaum, Hillside, NJ., 1987) pp. 95–143.Google Scholar
11.Schwartz, J.T. and Sharir, M., “A Survey of Motion Planning and Related Geometric Algorithms” Artificial Intelligence 37, 157–169 (1988).CrossRefGoogle Scholar
12.Erdmann, M. and Lozano-Perez, T., “On Multiple Moving Objects” IEEE International Conference on Robotics and Automation (1986) pp. 1419–1424.Google Scholar
13.Fujimura, K. and Samet, H., “Path Planning Among Moving Obstacles Using Spatial Indexing” IEEE International Conference on Robotics and Automation (1988) pp. 1662–1667.Google Scholar
14.Fujimura, K. and Samet, H., “A Hierarchical Strategy for Path Planning Among Moving Obstacles” IEEE Transactions on Robotics and Automation 61–69 (1989).CrossRefGoogle Scholar
15.Fujimura, K. and Samet, H. “Time Minimal Paths among Moving Obstacles” IEEE International Conference on Robotics and Automation (1989) pp. 1110–1115.Google Scholar
16.Fujimura, K. and Samet, H., “Motion Planning in a Dynamic Domain” Proceedings of the IEEE International Conference on Robotics and Automation (1990) pp. 324–330.CrossRefGoogle Scholar
17.Reif, J. and Sharir, M., “Motion Planning in the Presence of Moving Obstacles” IEEE International Conference on Foundations of Computer Science (1985) pp. 144–154.Google Scholar
18.Canny, J., “A New Algebraic Method for Robot Motion Planning and Real Geometry” IEEE International Conference on Foundations of Computer Science (1987) pp. 39–48.Google Scholar
19.Canny, J., “Exact Solution of Some Robot Motion Planning Problems” Robotics Research: The Fourth International Symposium (Bolles, R.C. and Roth, B., eds.). (The MIT Press, Cambridge, Massachusetts, 1988) pp. 505–513.Google Scholar
20.Aronov, B., Fortune, S. and Wilfong, G., Minimum Speed Motions (New York University, Dept. of Computer Science, Tech Report No. 389, 07 1988).Google Scholar
21.O'Dunlaing, C., “Motion Planning with Inertial Con- straints” Algorithmica 2, 431–475 (1987).CrossRefGoogle Scholar
22.Aronov, B., Fortune, S. and Wilfong, G., “Minimum Speed Motions” Int. J. Robotics Research 10, No. 3, 228–239 (06, 1991).CrossRefGoogle Scholar
23.Tychonievich, L., Zaret, D., Mantegna, J., Evans, R., Muehle, E. and Martin, S., “A Maneuvering-Board Approach to Path Planning with Moving Obstacles” Proceedings of the International Joint Conference on Artificial Intelligence (1989) pp. 1017–1021.Google Scholar
24.Kant, K. and Zucker, S.W., “Planning Collision-Free Trajectories in Time-Varying Environments: A Two-Level Hierarchy” IEEE International Conference on Robotics and Automation (1988) pp. 1644–1649.Google Scholar
25.Kant, K. and Zucker, S.W., “Toward Efficient Trajectory Planning: The Path-Velocity Decomposition” Int. J. Robotics Research 5, No. 3, 72–89 (Fall, 1986).CrossRefGoogle Scholar
26.Pan, T. and Luo, R.C., “Motion Planning for Mobile Robots in a Dynamic Environment with Moving Obstacles” IEEE International Conference on Robotics and Automation (1990) pp. 578–583.CrossRefGoogle Scholar
27.Khatib, O., “Real-Time Obstacle Avoidance for Manipula- tors and Mobile Robots” IEEE International Conference on Robotics and Automation (1985) pp. 500–505.Google Scholar
28.Slack, M.G. and Miller, D.P., “Route Planning in a Four-Dimensional Environment” JPL Workshop (01 1987).Google Scholar
29.Slack, M.G. and Miller, D.P., “Path Planning Through Time and Space in Dynamic Domains” Proceedings of the IJCAI (1987) pp. 1067–1070.Google Scholar
30.Gil de Lamadrid, J.F., Obstacle Avoidance for a Mobile Robot among Moving Obstacles (University of Minnesota, Computer Science Dept., Ph. D. Thesis, 1990).Google Scholar
31.Asano, T., Guibas, L.J., Hershberger, J. and Imai, H., “Visibility of Disjoint Polygons” Algorithmica 1, No. 1 49–63 (1986).CrossRefGoogle Scholar