Online Decision-Making for Scalable Autonomous Systems

Kyle Hollins Wray, Stefan J. Witwicki, Shlomo ZilbersteinIJCAI 2017 · DOI

TL;DR

This paper introduces MODIA, a novel framework for scalable online decision-making in autonomous systems, particularly for autonomous vehicles (AVs) navigating complex intersections. MODIA decomposes the problem into smaller, manageable decision components (DCs) and uses a lexicographic executor (LEAF) to combine their recommendations, achieving efficient and robust decision-making in real-world scenarios.

What Problem Does This Paper Address?

Autonomous vehicles (AVs) face a significant challenge in making split-second decisions at intersections, especially in open-world environments with an unpredictable number of other vehicles, pedestrians, and dynamic factors. Existing methods struggle with the sheer complexity and the need to plan under uncertainty when dealing with a vast and ever-changing set of interacting entities. This paper addresses the gap in scalable, theoretically grounded decision-making frameworks that can handle this dynamic complexity for AVs in real-time.

Methods

The core of the paper is the MODIA (Multiple Online Decision-components with Interacting actions) framework. MODIA works by:

  • Decomposition into Decision Problems (DPs): Pre-defined, solvable decision problems (e.g., for a single vehicle, a pedestrian) are created offline. These are typically modeled as Partially Observable Markov Decision Processes (POMDPs).
  • Online Instantiation of Decision Components (DCs): During execution, based on sensor input, relevant DPs are instantiated as DCs. Crucially, the number and type of DCs are not known a priori.
  • Lexicographic Executor Action Function (LEAF): To combine the recommendations from multiple DCs into a single action for the AV, the paper proposes LEAF. LEAF establishes a lexicographic preference order over the actions suggested by the DCs. It then selects the highest-ranked action according to this preference, ensuring a consistent and safe decision. This is a novel approach to action aggregation in this context.
  • Risk-Sensitive MODIA: The paper also introduces a risk-sensitive variant that penalizes high-risk actions, further enhancing safety.

Datasets

Not discussed in the paper. The authors mention using a realistic vehicle simulator and a real AV prototype for evaluation.

Key Insights and Ideas

  • Scalability through Decomposition: The key insight is that complex, real-world decision-making can be made tractable by decomposing it into smaller, manageable POMDPs (DCs) rather than attempting to solve a single, massive POMDP.
  • LEAF for Coherent Action Aggregation: The LEAF mechanism provides a principled way to resolve conflicts and combine recommendations from multiple independent decision-makers (DCs) into a single, coherent action for the agent. This is crucial for safety and efficiency.
  • Theoretical Guarantees for Online Decision-Making: The paper provides theoretical analysis of MODIA and LEAF, including complexity bounds and regret minimization properties, offering a strong foundation for its practical application.
  • Bridging Theory and Practice: The work demonstrates how a theoretically sound framework like MODIA can be effectively applied to a challenging real-world problem like AV intersection navigation.

Key Results

  • Improved Intersection Completion Times: In simulations, the MODIA AV successfully completed six different intersection scenarios faster than a naive AV baseline that waited for all other agents to clear the intersection.
  • Safety and Robustness: While the ignorant AV (which ignores other agents) was faster, the MODIA AV safely avoided potential incidents, demonstrating its robustness in handling complex interactions.
  • Scalability Demonstrated: The paper highlights how MODIA scales linearly with the number of interacting agents, contrasting with the exponential complexity of monolithic POMDPs for similar scenarios. For a 4-way stop with 3 other vehicles, MODIA uses 795 states distributed across three POMDPs, whereas a monolithic POMDP would have 640,000 states.
  • Real-World Prototype Integration: The MODIA and LEAF framework was successfully integrated and demonstrated on a real AV prototype navigating a 4-way intersection.

Limitations and Future Work

  • Computational Intractability of Optimal Executor: Proposition 2 shows that finding the absolute optimal executor is computationally intractable in practice, motivating the use of practical approaches like LEAF.
  • Unknown Number of DCs and Horizon: The framework is designed to handle an unknown number of DCs and their durations, but the theoretical analysis often assumes knowledge of a maximum number of DCs and horizon for decidability.
  • Future Work: The authors suggest exploring more sophisticated executors beyond LEAF and risk-sensitive MODIA. They also plan to develop additional DPs for AVs and apply MODIA to other intractable robotic domains, such as humanoid service robots.

Summary updated

BibTeX
@inproceedings{wray2017online,
  author = {Kyle Hollins Wray and Stefan J. Witwicki and Shlomo Zilberstein},
  title = {{Online Decision-Making for Scalable Autonomous Systems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/664},
}
Figure