The steady development of motor vehicle technology will enable cars of the near future to assume an ever increasing role in the decision making and control of the vehicle itself. In the foreseeable future, cars will have the ability to communicate with one another in order to better coordinate their motion. This motivates a number of interesting algorithmic problems. 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 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.


    Access

    Download


    Export, share and cite



    Title :

    On the Complexity of an Unregulated Traffic Crossing


    Contributors:

    Publication date :

    2015


    Type of media :

    Preprint


    Type of material :

    Electronic Resource


    Language :

    English




    UNREGULATED PEDESTRIAN CROSSING

    IVSHUKOV ALEKSEJ KONSTANTINOVICH | European Patent Office | 2017

    Free access

    LIGHTING ON UNREGULATED PEDESTRIAN CROSSING

    S. N. Pavlov / Yu. V. Pavlova | DOAJ | 2019

    Free access

    The way to improve safety of pedestrian traffic at unregulated pedestrian crossing

    Kalmykov Boris / Kalmykova Olga / Kalmykov Mihail | DOAJ | 2021

    Free access

    METHOD OF ROAD TRAFFIC CONTROL AT UNREGULATED CROSSWALK

    VAVILIN ALEKSANDR SERGEEVICH / SYCHIKOV DMITRIJ VASILEVICH | European Patent Office | 2018

    Free access

    USAGE OF SIMULATION MODELING FOR IMPROVEMENT OF SAFETY MANAGEMENT ON UNREGULATED PEDESTRIAN CROSSING

    Makarova, Irina / Khabibullin, Rifat / Mavrin, Vadim | TIBKAT | 2016

    Free access