Adaptive granular planning for robust plan generation under uncertain traffic conditions

Real-time execution of planned routes often requires re-planning, especially in highly dynamic environments. However, re-planning not only induces deterioration of solution quality - it is often time-consuming or even impossible. The article describes a new approach to solving Plan Generation Problems (PGPs), aimed at application for route planning in uncertain environments. The concept is based on maintaining a set of alternative solutions to allow quick switching when conditions change. A new formal representation of a PGP solution is proposed. Map abstraction methods are discussed in the context of landmarks defined by natural characteristics of urban areas. The article introduces the concept of solution robustness and presents methods for a priori prediction of solution feasibility under unreliable conditions. Finally, the paper presents strategies for execution of robust plans, as well as a formal definition of a plan execution problem. Several new possibilities are discussed, such as the inclusion of human decisions as feedback for intelligent route planning systems.