Contingency Planning for an Autonomous Land Vehicle

TL;DR

This paper introduces a novel route planning algorithm for autonomous land vehicles that explicitly handles uncertainty and incompleteness in map data. It precomputes contingency plans for potential blockages, leading to more robust and reliable navigation in unknown environments.

What Problem Does This Paper Address?

Autonomous vehicles operating in real-world environments face significant challenges due to imperfect and incomplete map data. Standard route planning algorithms often assume perfect knowledge, leading to brittle plans that fail when unexpected obstacles or impassable regions are encountered. This paper addresses the critical need for route planners that can:

  1. Avoid critical dependencies: Plans should not rely on uncertain events for their success.
  2. Preplan for contingencies: The system needs to anticipate alternative future possibilities and have pre-defined plans to handle them.
  3. Reason about information gathering: The planner should be able to evaluate the trade-off between obtaining more information and proceeding with the current knowledge.

Specifically, the authors highlight the problem of "choke regions" – narrow traversable paths between impassable areas. A small, unmapped obstacle in a choke region can necessitate a large detour, significantly impacting the overall route cost and feasibility. Existing methods often fail to account for these potential detours, making them less robust.

Methods

The core of the proposed solution is a modified hierarchical A* search algorithm. Key innovations include:

  • Semantic Network Representation: Terrain is represented as a semantic network of regions, including passable, impassable, and "choke" regions. This abstraction simplifies high-level planning.
  • Choke Region Identification: A specific method is used to identify choke regions based on map data, considering region size and internal features. These are crucial for identifying potential bottlenecks.
  • Contingency Planning: The algorithm explicitly precomputes alternative routes (contingency plans) that will be executed if a choke region is found to be blocked. These plans are embedded within the main plan.
  • Cost Function with Probabilities: The cost of a plan incorporates the probability of choke regions being traversable. The expected cost of detours is factored into the overall route cost, allowing for a more informed selection of the "best" route.
  • Hierarchical Planning: The algorithm operates in two stages: first, a high-level abstract plan is generated using the semantic network, and then detailed paths are planned for each segment using dynamic programming.
  • Max-Level Parameter: The planner can be configured to consider a specified number of simultaneous blockages (max-level) for contingency planning.

Datasets

Not discussed in the paper. The authors mention using map data for the Fulda Gap area in Germany and map data for the Martin Marietta ALV test site near Denver, Colorado, for testing and demonstration.

Key Insights and Ideas

  • Choke regions are critical: Identifying and explicitly planning for potential blockages in narrow "choke" regions is paramount for robust autonomous navigation.
  • Precomputation is key: Generating contingency plans before execution significantly reduces the computational burden and decision-making complexity during real-time operation.
  • Probabilistic cost estimation: Incorporating the probability of traversability for choke regions into the cost function allows for a more realistic assessment of route viability.
  • Hierarchical approach balances abstraction and detail: Using a high-level semantic network for initial planning and then detailed dynamic programming for path segments provides an efficient and effective strategy.

Key Results

  • The algorithm successfully generates routes that are more robust to map uncertainties compared to standard planners.
  • Contingency planning can lead to the selection of different "best" routes than those chosen without considering potential blockages.
  • Execution times for planning with one level of contingency were in the range of 10 to 60 minutes, which is considered reasonable for pre-mission planning in many mobile robot applications.
  • The majority of computation time is spent on dynamic programming for detailed path generation, suggesting that parallel processing or precomputation of path segments could significantly speed up the process.

Limitations and Future Work

  • Execution Time: While reasonable for pre-mission planning, the 10-60 minute execution times can be slow for debugging and testing.
  • Dynamic Programming Bottleneck: The computational cost of detailed path generation is a major bottleneck. Future work could involve:
  • Parallel Hardware: Exploiting parallel processing for dynamic programming.
  • Precomputation: Precomputing and storing detailed path segments for reuse.
  • Caching: Caching results of detailed path calculations.
  • Choke Region Complexity: The current implementation might not always generate the optimal route in complex choke regions with multiple exits. Future work could involve dividing such regions into smaller, two-exit choke regions.
  • Search Efficiency: Repeated generation and re-evaluation of contingent paths can be inefficient. Storing completed search tree branches could improve efficiency.
  • Shortcut Evaluation: The algorithm could be extended to evaluate "shortcuts" through areas that are probably not traversable but might be.
  • Information Gathering: The framework can be extended to evaluate the trade-offs involved in planning to obtain additional information (e.g., using sensors to verify bridge usability).
  • Non-linear Evaluation Functions: Using non-linear evaluation functions could handle more complex goals, such as time-critical arrivals.

Summary updated

BibTeX
@inproceedings{1987contingency,
  title = {{Contingency Planning for an Autonomous Land Vehicle}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure