Scheduling for Urban Air Mobility using Safe Learning

Surya Murthy, Natasha A. Neogi, Suda Bharadwaj

TL;DR

This paper tackles the complex scheduling problem for Urban Air Mobility (UAM) vehicles, aiming to minimize costs from missed soft deadlines while strictly guaranteeing all hard deadlines are met. They achieve this by modeling the problem as a Markov Decision Process (MDP), using safe learning to estimate uncertain trip times and demand, and employing Monte Carlo Tree Search (MCTS) with an Earliest Deadline First (EDF) policy to find near-optimal, non-preemptive schedules.

What Problem Does This Paper Address?

The burgeoning field of Urban Air Mobility (UAM) promises to revolutionize urban transportation with on-demand aerial vehicles. However, efficiently and safely scheduling these vehicles presents a significant challenge. UAM vehicles operate in an urban environment, receiving trip requests between vertiports in an aperiodic, on-demand manner. Each trip has an associated completion time (which can vary) and a deadline, which can be either "hard" (must be met) or "soft" (missing it incurs a cost). The core problem is to develop a scheduler that can operate online (without knowing future requests or exact trip durations in advance), guarantee all hard deadlines are met, and minimize the total cost incurred by missing soft deadlines. Existing scheduling approaches often struggle with the probabilistic nature of trip times and demand, and crucially, lack robust safety guarantees for hard deadlines.

Methods

The authors frame the UAM scheduling problem as a Markov Decision Process (MDP). To handle the inherent uncertainty in trip completion times and request arrival rates, they employ safe model-based learning. This involves:

  • MDP Construction: Defining the states (representing the configuration of active requests), actions (scheduling a specific request or remaining idle), transition probabilities, and reward functions (penalizing missed soft deadlines and heavily penalizing missed hard deadlines).
  • Safe Learning: Using a "pruning" technique on the MDP to remove paths that lead to hard deadline violations. This ensures that the learned model only considers "safe" trajectories.
  • Sampling: Traversing the pruned MDP to collect data and estimate the probability distributions for trip completion times and inter-arrival times.
  • Policy Optimization: Once an estimated MDP is built, they use Monte Carlo Tree Search (MCTS) with an Earliest Deadline First (EDF) simulation policy to find a near-optimal, non-preemptive scheduling strategy. EDF prioritizes requests with the closest deadlines, which is a standard heuristic for real-time systems. They also compare their MCTS approach to Value Iteration (VI), a more computationally intensive method for finding optimal policies.

A key distinction is the focus on non-preemptive scheduling, meaning once a trip is started, it must be completed before another can begin.

Datasets

The paper does not explicitly mention using pre-existing datasets. Instead, they create a synthetic benchmark based on a defined set of routes and requests with specified probabilistic distributions for trip completion times and inter-arrival times. This allows them to control the complexity and test their algorithms under various scenarios.

Key Insights and Ideas

  • Safety First: The core innovation is the emphasis on "safe learning" by pruning the MDP. This ensures that the learned model and subsequent policy inherently avoid hard deadline violations, a critical requirement for real-world UAM operations.
  • Probabilistic Modeling is Crucial: UAM is inherently uncertain. Accurately modeling trip completion times and demand as probability distributions is essential for effective scheduling.
  • MCTS with EDF as a Practical Solution: While VI can find optimal policies, its computational cost grows exponentially with state space size. MCTS, especially when guided by a strong heuristic like EDF, offers a scalable way to find near-optimal policies for complex, large-scale MDPs.
  • Non-Preemption Adds Complexity: The non-preemptive nature of the scheduling problem leads to a larger state space and, consequently, longer computation times compared to preemptive scheduling, highlighting the trade-offs in practical UAM operations.

Key Results

  • The developed safe learning approach successfully generates a non-preemptive scheduler that guarantees no hard deadlines are missed.
  • The scheduler effectively minimizes the average cost of missed soft deadlines.
  • Scalability: The approach demonstrates scalability with respect to the number of routes and the uncertainty in delay and demand distributions. Table 1 shows that the state space of the non-preemptive MDP grows more slowly than the preemptible one.
  • Performance Comparison: Figure 4 shows that Value Iteration (VI) achieves a lower average cost (better performance) than MCTS approximations. However, MCTS provides a near-optimal solution that is computationally more feasible for larger problems. The EDF-guided MCTS strategy significantly outperforms random action selection in MCTS.
  • The estimated MDP converges to the actual MDP with high accuracy (approximately 94%) with a reasonable number of samples (1000).

Limitations and Future Work

  • Limited Hard Request Complexity: The paper notes that inserting too many hard requests can lead to unschedulable systems, suggesting a limitation in handling highly constrained scenarios.
  • Focus on Non-Preemptive: While the paper addresses non-preemptive scheduling, future work could explore preemptive scenarios more deeply.
  • Future Work: The authors suggest future research directions including:
  • Improving scalability with respect to increasing numbers of hard requests.
  • Applying the approach to generate schedulers from existing UAM schedule databases.
  • Further exploration of preemptible vs. non-preemptible scheduling trade-offs.

Summary updated

Abstract

:This work considers the scheduling problem for Urban Air Mobility (UAM) vehicles travelling between origin-destination pairs with both hard and soft trip deadlines. Each route is described by a discrete probability distribution over trip completion times (or delay) and over inter-arrival times of requests (or demand) for the route along with a fixed hard or soft deadline. Soft deadlines carry a cost that is incurred when the deadline is missed. An online, safe scheduler is developed that ensures that hard deadlines are never missed, and that average cost of missing soft deadlines is minimized. The system is modelled as a Markov Decision Process (MDP) and safe model-based learning is used to find the probabilistic distributions over route delays and demand. Monte Carlo Tree Search (MCTS) Earliest Deadline First (EDF) is used to safely explore the learned models in an online fashion and develop a near-optimal non-preemptive scheduling policy. These results are compared with Value Iteration (VI) and MCTS (Random) scheduling solutions.
BibTeX
@inproceedings{murthy2022scheduling,
  author = {Surya Murthy and Natasha A. Neogi and Suda Bharadwaj},
  title = {{Scheduling for Urban Air Mobility using Safe Learning}},
  booktitle = {FMAS/ASYDE@SEFM},
  year = {2022},
  url = {https://openreview.net/forum?id=e53DasgKq2},
}
Figure