Booth Id:
SOFT055
Category:
Systems Software
Year:
2025
Finalist Names:
Doshi, Naman (School: North Sydney Boys High School)
Abstract:
Efficient traffic navigation algorithms are vital for reducing congestion, emissions, and delays in modern cities. Yet, existing systems use “selfish” routing — optimizing individual travel times — often causing bottlenecks as vehicles converge on the same paths. Achieving global efficiency necessitates agents to globally coordinate their planning. To address this, the author developed AutoFlow, a novel Multi-Agent Pathfinding (MAPF)-based algorithm tailored to real-world road networks. Unlike traditional grid-based MAPF literature, AutoFlow accounts for everyday constraints such as traffic lights and dynamically changing road conditions, alongside a novelly optimized space-time reservation table to track exact future road occupancy. AutoFlow introduces hill-climbing route refinement via rapid approximate simulations and leverages graph partitioning with contraction hierarchies for scalable performance. Parallelized across multiple CPU cores, it interfaces with Metropolis, a custom simulator the author built — capable of importing OpenStreetMap data and generating hyper realistic road networks up to 200 million m² in size. In tests, AutoFlow outperformed selfish routing by up to 20% in trip time and emissions — scaling exponentially with traffic density and map size. Only 40–60% adoption is needed to achieve 90% of total benefits, persisting under realistic conditions and in urban layouts like Manhattan. Even accounting for the added runtime of iterative route improvements, AutoFlow is 3-10x faster than traditional A* as the author reduced its runtime by the square root of the number of intersections in the road network. Beyond traffic management, AutoFlow also has significant potential applications in drone coordination and warehouse robotics.
Awards Won: