Abstract
The primary objective of this paper is to introduce the adaptive highways algorithm, a path planning algorithm for vehicles moving on a grid. We consider a workspace that consists of a symmetric grid and a large number of vehicles that move on the grid to accomplish a certain task. Each vehicle is assigned the task of visiting a set of randomly selected locations, which are updated over time. The dynamics of the vehicles are described by a constrained linear double-integrator model. The objective is to find, in real time, a set of trajectories that maximize the average speed of the vehicles while ensuring safety. The trajectory optimization problem is solved locally, whereas a central entity is employed for distribution of information. Safety guarantees are provided through a space reservation mechanism. Several algorithms are presented and compared in terms of performance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Frazzoli, E., Dahleh, M.A., Feron, E.: Real-time motion planning for agile autonomous vehicles. AIAA Journal of Guidance, Control, and Dynamics 25(1), 116–129 (2002)
Guizzo, E.: Three engineers, hundreds of robots, one warehouse. IEEE Spectrum 45(7), 22–29 (2008)
Kator, C.: Staples’ robotic retrievers offer new take on break-pack picking. In: Modern Materials Handling (2007)
Lavalle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006)
LaValle, S.M., Kuffner, J.J.: Randomized kinodynamic planning. In: Proceedings of the 1999 IEEE International Conference on Robotics and Automation, Denver, CO (August 2000)
Nagy, T.K., D’Andrea, R., Ganguly, P.: Near-optimal dynamic trajectory generation and control of an omnidirectional vehicle. Robotics and Autonomous Systems 46, 47–64 (2004)
Purwin, O., D’Andrea, R.: Trajectory generation and control for four wheeled omnidirectional vehicles. Robotics and Autonomous Systems 54(1), 13–22 (2006), doi:10.1016/j.robot.2005.10.002
Purwin, O., D’Andrea, R., Lee, J.W.: Theory and implementation of path planning by negotiation for decentralized agents. Robotics and Autonomous Systems (2007), doi:10.1016/j.robot.2007.09.020.
Raffard, R.L., Tomlin, C.J., Boyd, S.P.: Distributed optimization for cooperative agents: Application to Formation Flight. In: 43rd IEEE Conference on Decision and Control, Atlantis, Paradise Island, Bahamas, December 14-17 (2004)
Schouwenaars, T., How, J., Feron, E.: Decentralized cooperative trajectory planning of multiple aircraft with hard safety guarantees. In: AIAA Guidance, Navigation, and Control Conference and Exhibit, August 16-19. Providence, Rhode Island (2004)
Wurman, P.R., D’Andrea, R., Mountz, M.: Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Magazine 29(1), 9–19 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Roozbehani, H., D’Andrea, R. (2011). Adaptive Highways on a Grid. In: Pradalier, C., Siegwart, R., Hirzinger, G. (eds) Robotics Research. Springer Tracts in Advanced Robotics, vol 70. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19457-3_39
Download citation
DOI: https://doi.org/10.1007/978-3-642-19457-3_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19456-6
Online ISBN: 978-3-642-19457-3
eBook Packages: EngineeringEngineering (R0)