Contingency Planning for an Autonomous Land Vehicle

Abstract

A route planner for an autonomous land vehicle has been developed that deals explicitly with the incompleteness and uncertainties that can be expected in map data. In particular, the planner finds a preferred route taking into account the potential cost of the detours that may be needed if one or more choke regions are found to be blocked. In addition, it precomputes and saves the alternative or contingent routes that will be used if any of the potential detour areas are found to be blocked. The planner uses a semantic network representation for terrain which mp.kes it practical for a hierarchical version of an A sear ch algorithm to identify low cost routes where the cost of potential detours is factored into the cost of the route selected. A dynamic programming algorithm is integrated to plan detailed paths for each route segment, with this detailed planning exploiting all of the variations in expected costs which can be estimated based on whatever level of detail is available in the map.