The Taub Faculty of Computer Science Events and Talks

We study a geometrically constrained combinatorial problem inspired by the following scenario: autonomous vehicles move on a $m$-lane freeway, where $m \geq 2$. Each vehicle heads to some destination and is allowed to exit the road only through a designated exit lane when approaching its destination. We assume that vehicles have limited memory and sensing capabilities, and cannot directly communicate with their peers. We present a completely decentralized distributed algorithm that allows vehicles to get to the exit lane when necessary without collisions. We approach the solution in two steps. First, we show that a cellular automata based agent is capable to follow a complex path, visiting every cell on the grid. Then we show that even a $5$-year old kid, who is just learned to count to $10$, can navigate to exit the traffic on roads of any dimension, following a set of extremely simple rules.