Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T05:56:06.724Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  09 March 2009

Summary

Continuing the work presented in part I, ‡ 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. We define a locally minimum velocity path as an optimal robot trajectory, given only local information about obstacle trajectories. We 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. Our results apply to both robots with and without maximum velocity limits.

Type
Research Article
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.de Lamadrid, J.F. Gil and Zimmerman, J.L., “Avoidance of Obstacles with Unknown Trajectories: Locally Optimal Paths and Path Complexity, Part IRobotica 11, part 4, pp. 299308 (1993).CrossRefGoogle Scholar
2.Schwartz, J.T., Hopcroft, J. and Sharir, M., Planning, Geometry and Complexity of Robot Motion (Ablex Pub. Co., Norwood, NJ., 1987) pp. 267281.Google Scholar
3.Yap, C.K., “Algorithmic Motion Planning”, Algorithmic and Geometric Aspects of Robotics (Schwartz, J.T. and Yap, C.K., eds) (Lawrence Erlbaum, Hillside, NJ, 1987) pp. 951143.Google Scholar
4.Erdmann, M. and Lozano-Perez, T., “On Multiple Moving Objects”, IEEE International Conference on Robotics and Automation(1986) pp. 14191424.Google Scholar