Traffic Light Scheduling, Value of Time, and Incentives

Traffic Light Scheduling, Value of Time, and Incentives

Argyrios Deligkas, Erez Karpas, Ron Lavi, Rann Smorodinsky

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 4743-4749. https://doi.org/10.24963/ijcai.2018/659

We study the intersection signalling control problem for cars with heterogeneous valuations of time (VoT). We are interested in a control algorithm that has some desirable properties: (1) it induces cars to report their VoT truthfully, (2) it minimizes the value of time lost for cars waiting at the intersection, and (3) it is computationally efficient. We obtain three main results: (1) We describe a computationally efficient heuristic forward search approach to solve the static problem. Simulation results show that this method is significantly faster than the dynamic-programming approach to solve the static problem (which is by itself polynomial time). We therefore believe that our algorithm can be commercially implemented. (2) We extend the solution of the static problem to the dynamic case. We couple our algorithm with a carefully designed payment scheme which yields an incentive compatible mechanism. In other words, it is the best interest of each car to truthfully report its VoT. (3) We describe simulation results that compare the social welfare obtained by our scheduling algorithm, as measured by the total value of waiting time, to the social welfare obtained by other intersection signalling control methods.
Keywords:
Planning and Scheduling: Planning and Scheduling
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems