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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    On the Complexity of an Unregulated Traffic Crossing


    Beteiligte:
    Dasler, Philip (Autor:in) / Mount, David M. (Autor:in)

    Erscheinungsdatum :

    2015


    Medientyp :

    Preprint


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    UNREGULATED PEDESTRIAN CROSSING

    IVSHUKOV ALEKSEJ KONSTANTINOVICH | Europäisches Patentamt | 2017

    Freier Zugriff

    LIGHTING ON UNREGULATED PEDESTRIAN CROSSING

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

    Freier Zugriff

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

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

    Freier Zugriff

    METHOD OF ROAD TRAFFIC CONTROL AT UNREGULATED CROSSWALK

    VAVILIN ALEKSANDR SERGEEVICH / SYCHIKOV DMITRIJ VASILEVICH | Europäisches Patentamt | 2018

    Freier Zugriff

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

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

    Freier Zugriff