Treffer: Geometric Flows in Grids: Static, Dynamic, and In-Between

We designed and implemented efficient algorithms for finding trajectories for moving multiple disks among a set of static or dynamic obstacles. We are motivated by the problem in air traffic management of routing aircraft among hazardous weather cells. We consider three path routing paradigms: Static airlanes: A set of lanes for air traffic is established. The aircraft move “ducks-in-a-row” along each lane, altogether forming a highly coherent traffic pattern. The drawback is that the lanes, being static, do not stay clear of hazardous weather as the weather cells move. FreeFlight: Each aircraft determines its own trajectory in space-time, avoiding moving weather cells and other aircraft. This strategy can result in highly complex traffic patterns that are not amenable to human controller oversight. “Morphing noodles”: This model, introduced in the paper, combines the advantages of the static airlanes and the FreeFlight solution. The aircraft are routed along a set of lanes that slowly change as the weather cells move. This results in a correlated traffic flow amidst moving weather. The main feature of the noodles is that they never change their homotopy type w.r.t. the obstacles. Our path-finders are guided by hexagonal packing of disks in the free space, and a uniform discretization of the time. The implemented algorithms are dual-approximation ones: they find at least the maximum possible number of paths (but may be more) while compromising on the paths “thickness”. On the practical side, a set of domain-specific constraints is taken into account. 1