k-Stacks: High-density valet parking for automated vehicles

Automated valet parking not only improves driving comfort, but can have a considerable impact on the urban landscape by reducing the required parking space. We present the first study of parking space optimization for automated valet parking with an in-depth theoretical analysis of the parking lot properties under various aspects, inluding the worst-case extraction time, total shunting distance, and the number of shunting operations (each per car). Most importantly, the proposed model bounds all these values. We verify the theoretical properties of our model in four simulated scenarios, one of which is based on real-world data from a downtown parking garage. We show that very good pick-up times of about 1 min are possible with very little overhead in terms of shunting distance and time, while providing a significantly improved parking density as compared to conventional parking lots.