Abstract
One of the most challenging aspects of traffic coordination involves traffic intersections. In this paper we consider two formulations of a simple and fundamental geometric optimization problem involving coordinating the motion of vehicles through an intersection.
We are given a set of n vehicles in the plane, each modeled as a unit length line segment that moves monotonically, either horizontally or vertically, subject to a maximum speed limit. Each vehicle is described by a start and goal position and a start time and deadline. The question is whether, subject to the speed limit, there exists a collision-free motion plan so that each vehicle travels from its start position to its goal position prior to its deadline.
We present three results. We begin by showing that this problem is \(\mathsf {NP}\)-complete with a reduction from 3-SAT. Second, we consider a constrained version in which cars traveling horizontally can alter their speeds while cars traveling vertically cannot. We present a simple algorithm that solves this problem in \(O(n \log n)\) time. Finally, we provide a solution to the discrete version of the problem and prove its asymptotic optimality in terms of the maximum delay of a vehicle.
Supported by the National Science Foundation under grant CCF-1117259 and the Office of Naval Research under grant N00014-08-1-1015.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arkin, E.M., Mitchell, J.S.B., Polishchuk, V.: Maximum thick paths in static and dynamic environments. Comput. Geom. Theory Appl. 43(3), 279–294 (2010)
Au, T.-C., Stone, P.: Motion planning algorithms for autonomous intersection management. In: Bridging the Gap Between Task and Motion Planning (2010)
Berger, F., Klein, R.: A traveller’s problem. In: Proc. 26th Annu. Sympos. Comput. Geom., SoCG 2010, pp. 176–182. ACM, New York (2010)
Carlino, D., Boyles, S.D., Stone, P.: Auction-based autonomous intersection management. In: 2013 16th International IEEE Conference on Intelligent Transportation Systems-(ITSC), pp. 529–534. IEEE (2013)
Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Operations Res. 12(4), 568–581 (1964)
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Management Sci. 6(1), 80–91 (1959)
Dresner, K., Stone, P.: Multiagent traffic management: a reservation-based intersection control mechanism. In: Proc. Third Internat. Joint Conf. on Auton. Agents and Multi. Agent Syst., pp. 530–537. IEEE Computer Society (2004)
Dresner, K., Stone, P.: Multiagent traffic management: an improved intersection control mechanism. In: Proc. Fourth Internat. Joint Conf. on Auton. Agents and Multi. Agent Syst., pp. 471–477. ACM (2005)
Dresner, K.M., Stone, P.: A multiagent approach to autonomous intersection management. J. Artif. Intell. Res. 31, 591–656 (2008)
Fenton, R.E., Melocik, G.C., Olson, K.W.: On the steering of automated vehicles: Theory and experiment. IEEE Trans. Autom. Control 21(3), 306–315 (1976)
Fiorini, P., Shiller, Z.: Motion planning in dynamic environments using velocity obstacles. Internat. J. Robot. Res. 17(7), 760–772 (1998)
Hearn, R.A., Demaine, E.D.: Pspace-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theo. Comp. Sci. 343(1–2), 72–96 (2005)
Petti, S., Fraichard, T.: Safe motion planning in dynamic environments. In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005. (IROS 2005), pp. 2210–2215, August 2005
Rajamani, R.: Vehicle Dynamics and Control. Springer Science & Business Media, December 2011
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Res. 35(2), 254–265 (1987)
Van Middlesworth, M., Dresner, K., Stone, P.: Replacing the stop sign: unmanaged intersection control for autonomous vehicles. In: Proc. Seventh Internat. Joint Conf. on Auton. Agents and Multi. Agent Syst., pp. 1413–1416. International Foundation for Autonomous Agents and Multiagent Systems (2008)
Wurman, P.R., D’Andrea, R., Mountz, M.: Coordinating hundreds of cooperative, autonomous vehicles in warehouses. The AI magazine 29(1), 9–19 (2008)
Yu, J., LaValle, S.M.: Multi-agent path planning and network flow. In: Frazzoli, E., Lozano-Perez, T., Roy, N., Rus, D. (eds.) Algorithmic Foundations of Robotics X. Springer Tracts in Advanced Robotics, vol. 86, pp. 157–173. Springer, Heidelberg (2013). http://dx.doi.org/10.1007/978-3-642-36279-8_10
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Dasler, P., Mount, D.M. (2015). On the Complexity of an Unregulated Traffic Crossing. In: Dehne, F., Sack, JR., Stege, U. (eds) Algorithms and Data Structures. WADS 2015. Lecture Notes in Computer Science(), vol 9214. Springer, Cham. https://doi.org/10.1007/978-3-319-21840-3_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-21840-3_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21839-7
Online ISBN: 978-3-319-21840-3
eBook Packages: Computer ScienceComputer Science (R0)