Des métaheuristiques pour le guidage d’un solveur de contraintes dédié à la planification automatisée de véhicules

Abstract : This thesis, led in collaboration with Sagem Defence & Security, focuses on defining an efficient search strategy to solve vehicle path planning problems. This work addresses more precisely planning problems in which waypoints and "capacity" constraints (energy, radio bandwidth) are applied to vehicles.This document proposes an original approach, mixing an Ant Colony algorithm with an existing Constraint Programming solver. The former is used to fastly solve a relaxed version of the problem. The partial solution returned is then employed to guide the search of the latter, through a Probe Backtrack mechanism, towards the most promising areas of the state space. This approach allows to combine the metaheuristics solving fastness and the Constraint Programming completeness. We experimentally show that this approach meets the requirements for an on-line use of the planner.
Document type :
Theses
Complete list of metadatas

Cited literature [227 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00820318
Contributor : Abes Star <>
Submitted on : Friday, May 3, 2013 - 4:27:47 PM
Last modification on : Monday, November 12, 2018 - 11:00:38 AM
Long-term archiving on : Sunday, August 4, 2013 - 4:07:09 AM

File

2012ENMP0027.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : pastel-00820318, version 1

Citation

François Lucas. Des métaheuristiques pour le guidage d’un solveur de contraintes dédié à la planification automatisée de véhicules. Autre [cs.OH]. Ecole Nationale Supérieure des Mines de Paris, 2012. Français. ⟨NNT : 2012ENMP0027⟩. ⟨pastel-00820318⟩

Share

Metrics

Record views

1297

Files downloads

2719