Learning-based Preference Prediction for Constrained Multi-Criteria Path-Planning

Kevin Osanlou, Christophe Guettier, Andrei Bursuc, Tristan Cazenave, Eric JacopinarXiv 2021 · arXiv

Introduction

Navigating Autonomous Ground Vehicles (AGVs) through unpredictable off-road environments, such as disaster relief zones, presents a significant challenge. Traditional path-finding algorithms like A* typically prioritize the shortest path to conserve time and fuel. However, off-road conditions—characterized by steep slopes, heavy rain, or thick fog—can render a direct path unfeasible for a robot, necessitating costly human intervention. This research introduces a hybrid framework that balances travel distance with "autonomous feasibility" to minimize manual rescue operations.

Methodology: A Two-Stage Approach

The proposed system addresses the limitations of real-time physics simulations by using a learning-based proxy for environmental difficulty.

  1. Learning Autonomous Feasibility: Using the high-fidelity 4d Virtualiz 3D simulator, researchers generated thousands of missions under diverse weather and terrain conditions. A Multi-Layer Perceptron (MLP) was trained on this data to predict the probability that a specific path segment is "preferred" (i.e., navigable without intervention) based on features like rainfall, fog, wind, distance, and slope.
  2. Constraint-Based Planning: These predictions are integrated into a Probe-based Constraint Multi-Criteria Optimizer (PCMCO). This optimizer uses a flow formulation to ensure path consistency while simultaneously minimizing total distance and maximizing predicted autonomy.

Experimental Scenario

The framework was evaluated using a search-and-rescue scenario in a flooded region near Troyes, France. A graph representing real-world terrain was used to generate 200 random mission instances for benchmarking.

Map of the search-and-rescue mission area near Troyes, France, showing the graph-based path planning environment.

Key Results and the Distance-Autonomy Trade-off

The "NN + PCMCO" approach was benchmarked against a standard distance-only optimizer (PCO). The results demonstrate a clear trade-off: increasing path length can significantly improve autonomous success rates.

Comparison of distance and human interventions between the standard PCO and the proposed NN + PCMCO method across weather conditions.
  • Fine Weather: The hybrid model reduced human interventions from 1.6 to 0.1 per mission, requiring only a 10% increase in distance.
  • Moderate Weather: A 30% increase in distance allowed the AGV to avoid almost all interventions (dropping from 2.3 to 0.4).
  • Difficult Weather: In hostile conditions, the model cut interventions nearly in half (2.5 vs 4.1), despite a 22% distance penalty.

The neural network achieved 79% accuracy in predicting feasibility, significantly outperforming a baseline logistic regression model (71%).

Conclusion

This research quantifies the "cost of autonomy" in off-road navigation. By using a high-fidelity simulator to pre-calculate environmental risks into a lightweight neural network, AGVs can make informed decisions that prioritize mission success over mere distance. Future work will focus on enhancing feature engineering with raw sensor data and validating the system on physical hardware in real-world muddy conditions.

Summary updated

Abstract

Learning-based methods are increasingly popular for search algorithms in single-criterion optimization problems. In contrast, for multiple-criteria optimization there are significantly fewer approaches despite the existence of numerous applications. Constrained path-planning for Autonomous Ground Vehicles (AGV) is one such application, where an AGV is typically deployed in disaster relief or search and rescue applications in off-road environments. The agent can be faced with the following dilemma : optimize a source-destination path according to a known criterion and an uncertain criterion under operational constraints. The known criterion is associated to the cost of the path, representing the distance. The uncertain criterion represents the feasibility of driving through the path without requiring human intervention. It depends on various external parameters such as the physics of the vehicle, the state of the explored terrains or weather conditions. In this work, we leverage knowledge acquired through offline simulations by training a neural network model to predict the uncertain criterion. We integrate this model inside a path-planner which can solve problems online. Finally, we conduct experiments on realistic AGV scenarios which illustrate that the proposed framework requires human intervention less frequently, trading for a limited increase in the path distance.
BibTeX
@misc{osanlou2021learning,
  author = {Kevin Osanlou and Christophe Guettier and Andrei Bursuc and Tristan Cazenave and Eric Jacopin},
  title = {{Learning-based Preference Prediction for Constrained Multi-Criteria Path-Planning}},
  year = {2021},
  eprint = {2108.01080},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2108.01080},
}
Figure