Using a Variational Autoencoder to Learn Valid Search Spaces of Safely Monitored Autonomous Robots for Last-Mile Delivery

Peter J. Bentley, Soo Ling Lim, Paolo Arcaini, Fuyuki IshikawaarXiv 2023 · arXiv

TL;DR

This paper applies a hybrid machine learning and evolutionary algorithm approach called COIL to solve a critical real-world problem: scheduling last-mile delivery robots under strict human-monitoring constraints. By using a Variational Autoencoder (VAE) to map out a "safe" search space, the proposed method consistently finds valid schedules where standard Genetic Algorithms fail, while running 10% faster during daily re-optimization.

What Problem Does This Paper Address?

Last-mile delivery using autonomous robots is an eco-friendly and labor-saving alternative to traditional delivery vans. However, in real-world deployments (such as those trialed by the paper's industry partner, Panasonic), these robots aren't entirely unsupervised; human operators must remotely monitor them to intervene during tricky situations, like navigating crowded sidewalks.

Because human attention is a finite resource, there is a strict safety constraint: the number of robots operating simultaneously cannot exceed a specific threshold ($RT$). This creates a challenging optimization problem: how do you schedule robot start times and durations to maximize fulfilled customer deliveries without ever exceeding the safe monitoring limit? Standard optimization techniques struggle here because the valid search space is highly constrained and fractured.

Methods

The authors tackle this by adapting COIL (Constrained Optimization in Learned Latent Space), a hybrid framework combining unsupervised machine learning with evolutionary computation.

Instead of searching the raw, highly invalid problem space directly, COIL operates in three steps:

  1. Dataset Generation: A simple data-generating Genetic Algorithm (GA) runs offline to find a large set of diverse robot schedules that strictly satisfy the safety constraint (ignoring the delivery objective for now).
  2. Latent Space Learning: A Variational Autoencoder (VAE) is trained on this dataset. The VAE learns to compress these high-dimensional valid schedules into a lower-dimensional, continuous latent space ($\bar{z}$).
  3. Optimization: A second GA searches within this learned latent space to maximize the number of fulfilled delivery requests. Because the VAE's decoder maps latent vectors back to valid physical schedules, the GA is heavily biased toward exploring only safe solutions.
Figure 3: Constrained optimization in learned latent space (COIL) applied to real-world autonomous robot scheduling problem.

The authors compare COIL against a standard baseline GA that utilizes tournament selection to balance constraint satisfaction and objective maximization in the raw search space.

Datasets

The paper evaluates the algorithms using synthetic problem instances modeled after real-world parameters from Panasonic's trials:

  • Customer Requests: Sets of 120 to 240 random delivery requests with durations ranging from 60 to 360 minutes, distributed across a 12-hour working day.
  • Training Data: Datasets of valid schedules containing $2,500$, $5,000$, $7,500$, or $10,000$ unique data points generated by the offline GA to train the VAE.

Key Insights and Ideas

  • Standard GAs "Cheat" on Hard Constraints: When safety constraints are tight, standard GAs fail completely. They maximize the delivery objective by simply ignoring the safety threshold, producing schedules that are unusable in the real world.
  • The Dimensionality "Sweet Spot": The authors discovered that reducing the number of latent variables ($maxlv$) below the original problem dimensionality actually improves optimization performance and VAE training speed. However, reducing it too much degrades the VAE's reconstruction quality, revealing a clear performance "sweet spot."
  • Latent Spaces Smooth the Search: Searching within a space pre-filtered by a VAE allows the evolutionary algorithm to find high-quality solutions rapidly without wasting evaluations on invalid regions.

Key Results

  • Constraint Satisfaction: COIL successfully found valid solutions (zero safety constraints broken) across all tested design variations. In contrast, the baseline GA failed to find a single valid solution in difficult scenarios, averaging 44.7 constraint violations per run.
  • Execution Speed: While COIL requires an intensive offline pre-computation step to train the VAE, its online daily optimization phase is 10% faster than the baseline GA (1.81 minutes vs 1.89 minutes for 100 runs). This makes it highly practical for daily morning rescheduling as new customer orders arrive.
Comparison of GA vs COIL Optimization Paths

Limitations and Future Work

  • High Offline Overhead: Generating the initial dataset of valid solutions is computationally expensive, taking up to 25.8 hours for 10,000 data points in the most constrained scenarios.
  • Simplified Simulation: The current model assumes fixed robot speeds and relies on a basic first-come, first-served scheduling heuristic to allocate requests to individual robots.
  • Future Directions: The authors plan to explore advanced quality-diversity algorithms like MAP-Elites to accelerate the offline data generation phase, and intend to integrate more complex real-world variables, such as varying robot speeds and advanced fleet schedulers.

Summary updated

Abstract

The use of autonomous robots for delivery of goods to customers is an exciting new way to provide a reliable and sustainable service. However, in the real world, autonomous robots still require human supervision for safety reasons. We tackle the realworld problem of optimizing autonomous robot timings to maximize deliveries, while ensuring that there are never too many robots running simultaneously so that they can be monitored safely. We assess the use of a recent hybrid machine-learningoptimization approach COIL (constrained optimization in learned latent space) and compare it with a baseline genetic algorithm for the purposes of exploring variations of this problem. We also investigate new methods for improving the speed and efficiency of COIL. We show that only COIL can find valid solutions where appropriate numbers of robots run simultaneously for all problem variations tested. We also show that when COIL has learned its latent representation, it can optimize 10% faster than the GA, making it a good choice for daily re-optimization of robots where delivery requests for each day are allocated to robots while maintaining safe numbers of robots running at once.
BibTeX
@misc{bentley2023using,
  author = {Peter J. Bentley and Soo Ling Lim and Paolo Arcaini and Fuyuki Ishikawa},
  title = {{Using a Variational Autoencoder to Learn Valid Search Spaces of Safely Monitored Autonomous Robots for Last-Mile Delivery}},
  year = {2023},
  eprint = {2303.03211},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.03211},
}
Figure