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