Navigation : Index | << State-Space | Heuristics >>
A la fin de ce notebook, vous saurez :
Fast Downward est l’un des planificateurs les plus celebres en IA. Developpe par Malte Helmert (Universite de Bale) en 2006, il a remporte de nombreuses competitions IPC (International Planning Competition).
| Date | Événement |
|---|---|
| 2006 | Publication originale par Helmert |
| 2008 | Première victoire a l’IPC |
| 2011 | Introduction de LAMA (Lazy A* with Multi-Heuristics) |
| 2014 | Victoire IPC avec LAMA-first |
| 2024 | Toujours la reference pour la planification optimale |
Fast Downward se distingue par :
flowchart TD
P["PDDL (domaine + problème)"] --> T["TRANSLATOR (Python) — parse le PDDL, construit la tâche SAS+"]
T --> R["PREPROCESSOR (C++) — normalise, simplifie, élimine des variables"]
S["SEARCH ENGINE (C++) — recherche heuristique (A*, GBFS, etc.)"]
R --> S
S --> Q["Plan (actions)"]| Composant | Langage | Rôle |
|---|---|---|
| Translator | Python | Parse PDDL, construit la tâche SAS+ |
| Preprocessor | C++ | Normalise, simplifie, elimine variables |
| Search | C++ | Recherche heuristique dans l’espace d’etats |
Verifions que Docker et unified-planning sont disponibles, puis configurons l’acces a Fast Downward.
# Imports et detection de l'environnement
import sys
import os
import platform
import subprocess
import tempfile
import time
from pathlib import Path
# Informations systeme
OS_NAME = platform.system()
IS_WINDOWS = OS_NAME == 'Windows'
print(f"Systeme: {OS_NAME}")
print(f"Python: {sys.version_info.major}.{sys.version_info.minor}")
print(f"Repertoire de travail: {os.getcwd()}")Systeme: Windows
Python: 3.13
Repertoire de travail: <repo>MyIA.AI.Notebooks\SymbolicAI\Planners\02-ClassicalFast Downward est execute via l’image Docker jsboige/coursia-fast-downward qui fournit un serveur HTTP sur le port 8200.
# Verification de Docker
def check_docker():
"""Verifie si Docker est disponible."""
try:
result = subprocess.run(
['docker', '--version'],
capture_output=True, text=True, timeout=10
)
return result.returncode == 0, result.stdout.strip()
except FileNotFoundError:
return False, "Docker non installe"
except Exception as e:
return False, str(e)
DOCKER_OK, DOCKER_INFO = check_docker()
print(f"Docker: {'OK - ' + DOCKER_INFO if DOCKER_OK else 'NON DISPONIBLE - ' + DOCKER_INFO}")Docker: OK - Docker version 29.4.3, build 055a478Verification de la disponibilite de l’image Docker jsboige/coursia-fast-downward et lancement du conteneur avec le serveur HTTP Fast Downward sur le port 8200.
# Verification et lancement du conteneur Fast Downward
FAST_DOWNWARD_IMAGE = "jsboige/coursia-fast-downward:latest"
FD_API_PORT = 8200
FD_CONTAINER_NAME = "coursia-fast-downward"
def check_image_exists(image_name):
"""Verifie si une image Docker existe localement."""
try:
result = subprocess.run(
['docker', 'images', '-q', image_name],
capture_output=True, text=True, timeout=5
)
return bool(result.stdout.strip())
except Exception:
return False
def pull_image(image_name):
"""Telecharge une image Docker."""
print(f"Telechargement de {image_name}...")
result = subprocess.run(
['docker', 'pull', image_name],
capture_output=True, text=True, timeout=300
)
if result.returncode == 0:
print("Image telechargee avec succes")
return True
else:
print(f"Erreur: {result.stderr}")
return False
def start_fd_container():
"""Lance le conteneur Fast Downward avec le serveur HTTP."""
import urllib.request
# Arreter un eventuel conteneur existant
subprocess.run(['docker', 'rm', '-f', FD_CONTAINER_NAME],
capture_output=True, text=True, timeout=10)
cmd = [
'docker', 'run', '-d',
'--name', FD_CONTAINER_NAME,
'-p', f'{FD_API_PORT}:{FD_API_PORT}',
FAST_DOWNWARD_IMAGE
]
result = subprocess.run(cmd, capture_output=True, text=True, timeout=30)
if result.returncode != 0:
print(f"Erreur lancement conteneur: {result.stderr}")
return False
# Attendre que le serveur HTTP soit pret
import urllib.error
for attempt in range(15):
try:
resp = urllib.request.urlopen(
f"http://localhost:{FD_API_PORT}/health", timeout=2
)
if resp.status == 200:
print(f"Conteneur Fast Downward pret (port {FD_API_PORT})")
return True
except (urllib.error.URLError, ConnectionError):
time.sleep(1)
print("Timeout: le conteneur n'a pas repondu dans les 15s")
return False
if DOCKER_OK:
if check_image_exists(FAST_DOWNWARD_IMAGE):
print(f"Image {FAST_DOWNWARD_IMAGE} deja presente localement")
else:
pull_image(FAST_DOWNWARD_IMAGE)
FD_DOCKER_OK = start_fd_container()
else:
FD_DOCKER_OK = False
print("Fast Downward via Docker non disponible")Image jsboige/coursia-fast-downward:latest deja presente localement
Conteneur Fast Downward pret (port 8200)La bibliotheque unified-planning permet d’interagir avec Fast Downward de facon programmatique.
# Verification de unified-planning
try:
import unified_planning as up
from unified_planning.shortcuts import *
print(f"unified-planning version: {up.__version__}")
UP_OK = True
except ImportError:
print("unified-planning non installe. pip install unified-planning")
UP_OK = False
# Verification du plugin Fast Downward
try:
from up_fast_downward import FastDownwardPDDLPlanner
print("Plugin up-fast-downward disponible")
UP_FD_OK = True
except ImportError:
print("Plugin up-fast-downward non installe. pip install up-fast-downward")
UP_FD_OK = Falseunified-planning version: 1.3.0
Plugin up-fast-downward disponibleRésultat obtenu : L’audit de l’environnement revele les outils disponibles.
| Composant | Statut | Version |
|---|---|---|
| Docker | OK | 29.4.3 |
| Image FD Docker | Disponible | jsboige/coursia-fast-downward:latest |
| Serveur HTTP FD | Port 8200 | API /plan + /health |
| unified-planning | Installe | 1.3.0 |
| Plugin up-fast-downward | Disponible | Pret |
Points cles : - L’image Docker jsboige/coursia-fast-downward embarque Fast Downward avec un serveur HTTP sur le port 8200 - L’API /plan accepte un JSON {domain, problem, search} et retourne {returncode, stdout, stderr} - Le plugin up-fast-downward peut fonctionner si le binaire Fast Downward est installe localement - unified-planning offre des alternatives comme Pyperplan (pur Python) ou Tamer comme repli
Creons une fonction Python pour executer Fast Downward via Docker de maniere transparente.
def run_fast_downward_docker(domain_pddl: str, problem_pddl: str,
search_config: str = "astar(lmcut())",
timeout: int = 60) -> dict:
"""
Execute Fast Downward via l'API HTTP du conteneur Docker.
Args:
domain_pddl: Contenu du fichier domaine PDDL
problem_pddl: Contenu du fichier probleme PDDL
search_config: Configuration de recherche (defaut: A* avec LM-cut)
timeout: Timeout en secondes
Returns:
dict avec 'success', 'stdout', 'stderr', 'error', 'time'
"""
import json
import urllib.request
import urllib.error
if not DOCKER_OK or not FD_DOCKER_OK:
return {"success": False, "error": "Fast Downward Docker non disponible"}
payload = json.dumps({
"domain": domain_pddl,
"problem": problem_pddl,
"search": search_config,
}).encode("utf-8")
url = f"http://localhost:{FD_API_PORT}/plan"
req = urllib.request.Request(
url, data=payload,
headers={"Content-Type": "application/json"},
method="POST",
)
try:
start_time = time.time()
with urllib.request.urlopen(req, timeout=timeout) as resp:
data = json.loads(resp.read().decode("utf-8"))
elapsed = time.time() - start_time
if data.get("returncode") == 0:
return {
"success": True,
"stdout": data.get("stdout", ""),
"stderr": data.get("stderr", ""),
"time": elapsed,
}
else:
return {
"success": False,
"stdout": data.get("stdout", ""),
"stderr": data.get("stderr", ""),
"error": data.get("stderr", "") or data.get("stdout", ""),
"time": elapsed,
}
except urllib.error.URLError as e:
return {"success": False, "error": f"Connexion echouee: {e}", "time": 0}
except Exception as e:
return {"success": False, "error": str(e), "time": 0}
print("Fonction run_fast_downward_docker() prete (API HTTP)")Fonction run_fast_downward_docker() prete (API HTTP)Le translator convertit les fichiers PDDL en une representation interne SAS+ (Simplified Action Structures). Cette étape est cruciale pour l’efficacite du planificateur.
| PDDL | SAS+ |
|---|---|
| Predicats symboliques | Variables multi-valuees |
| Actions avec paramètres | Opérateurs instanties |
| Grande expressivite | Encodage compact |
| Parsing lourd | Recherche rapide |
Le fichier output.sas contient :
begin_version
3
end_version
begin_metric
1
end_metric
5 # Nombre de variables
begin_variable
var0
-1
3 # Nombre de valeurs possibles
Atom on(a, b)
Atom on(a, c)
Atom ontable(a)
end_variable
...# Exemple de domaine Blocks World simplifie
DOMAIN_BLOCKS = """
(define (domain blocks)
(:requirements :strips :typing)
(:types block)
(:predicates
(on ?x - block ?y - block)
(ontable ?x - block)
(clear ?x - block)
(handempty)
(holding ?x - block)
)
(:action pick-up
:parameters (?x - block)
:precondition (and (clear ?x) (ontable ?x) (handempty))
:effect (and (not (ontable ?x)) (not (clear ?x))
(not (handempty)) (holding ?x))
)
(:action put-down
:parameters (?x - block)
:precondition (holding ?x)
:effect (and (not (holding ?x)) (clear ?x)
(handempty) (ontable ?x))
)
(:action stack
:parameters (?x - block ?y - block)
:precondition (and (holding ?x) (clear ?y))
:effect (and (not (holding ?x)) (not (clear ?y))
(clear ?x) (handempty) (on ?x ?y))
)
(:action unstack
:parameters (?x - block ?y - block)
:precondition (and (on ?x ?y) (clear ?x) (handempty))
:effect (and (not (on ?x ?y)) (not (clear ?x))
(not (handempty)) (holding ?x) (clear ?y))
)
)
"""
# Probleme simple: empiler A sur B
PROBLEM_SIMPLE = """
(define (problem blocks-simple)
(:domain blocks)
(:objects a b - block)
(:init
(ontable a) (ontable b)
(clear a) (clear b)
(handempty)
)
(:goal (on a b))
)
"""
print("Domaine et probleme PDDL definis")
print(f"Domaine: blocks")
print(f"Probleme: empiler A sur B")Domaine et probleme PDDL definis
Domaine: blocks
Probleme: empiler A sur BExécution de Fast Downward via Docker sur le problème Blocks World avec l’algorithme A* et l’heuristique LM-cut, puis affichage du plan et des statistiques de recherche.
# Test avec Fast Downward - A* + LM-cut
if DOCKER_OK and FD_DOCKER_OK:
result = run_fast_downward_docker(
DOMAIN_BLOCKS, PROBLEM_SIMPLE,
search_config="astar(lmcut())",
timeout=30
)
print("=== Fast Downward: A* + LM-cut ===")
print(f"Succes: {result['success']}")
print(f"Temps: {result['time']:.2f}s")
if result['success']:
print("\n--- Sortie ---")
print(result['stdout'][-2000:] if len(result['stdout']) > 2000 else result['stdout'])
else:
print(f"Erreur: {result.get('error', 'Inconnue')}")
else:
print("Docker ou Fast Downward non disponible")=== Fast Downward: A* + LM-cut ===
Succes: True
Temps: 0.26s
--- Sortie ---
=0.002193s, 10692 KB] peak memory difference for successor generator creation: 0 KB
[t=0.002219s, 10692 KB] time for successor generation creation: 0.000015s
[t=0.002229s, 10692 KB] Variables: 5
[t=0.002258s, 10692 KB] FactPairs: 12
[t=0.002268s, 10692 KB] Bytes per state: 4
[t=0.002286s, 10692 KB] Conducting best first search with reopening closed nodes, (real) bound = 2147483647
[t=0.002318s, 10692 KB] New best heuristic value for lmcut: 2
[t=0.002344s, 10692 KB] g=0, 1 evaluated, 0 expanded
[t=0.002356s, 10692 KB] f = 2, 1 evaluated, 0 expanded
[t=0.002368s, 10692 KB] Initial heuristic value for lmcut: 2
[t=0.002378s, 10692 KB] pruning method: none
[t=0.002401s, 10692 KB] New best heuristic value for lmcut: 1
[t=0.002436s, 10692 KB] g=1, 3 evaluated, 1 expanded
[t=0.002452s, 10692 KB] New best heuristic value for lmcut: 0
[t=0.002638s, 10692 KB] g=2, 4 evaluated, 2 expanded
[t=0.002712s, 10692 KB] Solution found!
[t=0.002813s, 10692 KB] Actual search time: 0.000479s
pick-up a (1)
stack a b (1)
[t=0.002874s, 10692 KB] Plan length: 2 step(s).
[t=0.002874s, 10692 KB] Plan cost: 2
[t=0.002874s, 10692 KB] Expanded 3 state(s).
[t=0.002874s, 10692 KB] Reopened 0 state(s).
[t=0.002874s, 10692 KB] Evaluated 4 state(s).
[t=0.002874s, 10692 KB] Evaluations: 4
[t=0.002874s, 10692 KB] Generated 4 state(s).
[t=0.002874s, 10692 KB] Dead ends: 0 state(s).
[t=0.002874s, 10692 KB] Expanded until last jump: 0 state(s).
[t=0.002874s, 10692 KB] Reopened until last jump: 0 state(s).
[t=0.002874s, 10692 KB] Evaluated until last jump: 1 state(s).
[t=0.002874s, 10692 KB] Generated until last jump: 0 state(s).
[t=0.002874s, 10692 KB] Number of registered states: 4
[t=0.002874s, 10692 KB] Int hash set load factor: 4/4 = 1.000000
[t=0.002874s, 10692 KB] Int hash set resizes: 2
[t=0.002874s, 10692 KB] Search time: 0.000588s
[t=0.002874s, 10692 KB] Total time: 0.002874s
Solution found.
Peak memory: 10692 KB
Remove intermediate file output.sas
search exit code: 0
INFO Planner time: 0.17s
La sortie de Fast Downward contient plusieurs informations cles :
| Section | Contenu |
|---|---|
| Translation | Conversion PDDL vers SAS+ (nombre de variables, opérateurs) |
| Preprocessing | Simplification, elimination de variables, axiomes |
| Search | Progression de la recherche, noeuds expanses, temps |
| Solution | Sequence d’actions du plan, cout total |
Points cles : - Le nombre de variables SAS+ est typiquement inferieur aux predicats PDDL - L’heuristique LM-cut est admissible (garantit optimalite avec A*) - Le temps de recherche depend de la difficulte du problème
Fast Downward supporte plusieurs algorithmes de recherche. Voici les principaux :
A* utilise la fonction d’evaluation \(f(n) = g(n) + h(n)\) ou : - \(g(n)\) = cout accumule depuis l’etat initial - \(h(n)\) = estimation heuristique du cout restant
Avec une heuristique admissible, A* garantit de trouver la solution optimale.
# Comparaison des algorithmes de recherche
# Probleme plus complexe: tour de 3 blocs
PROBLEM_TOWER = """
(define (problem blocks-tower)
(:domain blocks)
(:objects a b c - block)
(:init
(ontable a) (ontable b) (ontable c)
(clear a) (clear b) (clear c)
(handempty)
)
(:goal (and (on a b) (on b c)))
)
"""
# Configurations a tester
SEARCH_CONFIGS = [
("A* + blind", "astar(blind())"),
("A* + LM-cut", "astar(lmcut())"),
("A* + FF", "astar(ff())"),
("A* + hmax", "astar(hmax())"),
]
results = []
if DOCKER_OK and FD_DOCKER_OK:
print("=== Comparaison des algorithmes de recherche ===")
print(f"{'Algorithme':<20} {'Succes':<10} {'Temps':<10} {'Info'}")
print("-" * 60)
for name, config in SEARCH_CONFIGS:
result = run_fast_downward_docker(
DOMAIN_BLOCKS, PROBLEM_TOWER,
search_config=config,
timeout=30
)
success_str = "OK" if result['success'] else "ECHEC"
time_str = f"{result['time']:.2f}s"
# Extraire le cout du plan si succes
if result['success']:
# Chercher "Plan cost: X" dans la sortie
import re
cost_match = re.search(r'Plan cost:\s*(\d+)', result['stdout'])
info = f"Cout: {cost_match.group(1)}" if cost_match else "Plan trouve"
else:
info = result.get('error', 'Inconnue')[:30]
print(f"{name:<20} {success_str:<10} {time_str:<10} {info}")
results.append((name, result))
else:
print("Docker non disponible - test impossible")=== Comparaison des algorithmes de recherche ===
Algorithme Succes Temps Info
------------------------------------------------------------
A* + blind OK 0.12s Cout: 4
A* + LM-cut OK 0.12s Cout: 4
A* + FF OK 0.13s Cout: 4
A* + hmax OK 0.15s Cout: 4| Algorithme | Admissible | Optimal | Rapidite |
|---|---|---|---|
| A* + blind | Oui | Oui | Lent (BFS degenere) |
| A* + LM-cut | Oui | Oui | Moyen |
| A* + FF | Non | Non garanti | Rapide |
| A* + hmax | Oui | Oui | Rapide (mais h faible) |
Observations : - blind() est equivalente a Dijkstra/BFS (pas de guidage) - LM-cut est la meilleure heuristique admissible pour l’optimalite - FF peut trouver des solutions rapidement mais non garanties optimales
Greedy Best-First Search (GBFS) utilise uniquement l’heuristique \(h(n)\) pour guider la recherche. Elle est plus rapide mais ne garantit pas l’optimalite.
\[f(n) = h(n)\]
Il existe deux variantes : - eager_greedy : Expansions immediates de tous les successeurs - lazy_greedy : Evaluation retardee des heuristiques (plus efficace)
# Test de Greedy Best-First Search
GREEDY_CONFIGS = [
("Eager Greedy + FF", "eager_greedy([ff()])"),
("Lazy Greedy + FF", "lazy_greedy([ff()])"),
("Eager Greedy + CG", "eager_greedy([cg()])"),
]
if DOCKER_OK and FD_DOCKER_OK:
print("=== Greedy Best-First Search ===")
print(f"{'Algorithme':<25} {'Succes':<10} {'Temps':<10} {'Info'}")
print("-" * 60)
for name, config in GREEDY_CONFIGS:
result = run_fast_downward_docker(
DOMAIN_BLOCKS, PROBLEM_TOWER,
search_config=config,
timeout=30
)
success_str = "OK" if result['success'] else "ECHEC"
time_str = f"{result['time']:.2f}s"
if result['success']:
import re
cost_match = re.search(r'Plan cost:\s*(\d+)', result['stdout'])
info = f"Cout: {cost_match.group(1)}" if cost_match else "Plan trouve"
else:
info = result.get('error', 'Inconnue')[:30]
print(f"{name:<25} {success_str:<10} {time_str:<10} {info}")=== Greedy Best-First Search ===
Algorithme Succes Temps Info
------------------------------------------------------------
Eager Greedy + FF OK 0.11s Cout: 4
Lazy Greedy + FF OK 0.11s Cout: 4
Eager Greedy + CG OK 0.11s Cout: 4Enforced Hill Climbing est un algorithme de recherche locale qui cherche a ameliorer continuellement la valeur heuristique. Si aucune amelioration n’est trouvee, il effectue une recherche en largeur (BFS) pour trouver un etat ameliorant.
Caractéristiques : - Très rapide pour les problemes faciles - Peut echouer sur les problemes difficiles (locaux optimaux) - Utilise souvent avec l’heuristique FF
# Test de EHC
EHC_CONFIG = "ehc([ff()])"
if DOCKER_OK and FD_DOCKER_OK:
print("=== Enforced Hill Climbing ===")
result = run_fast_downward_docker(
DOMAIN_BLOCKS, PROBLEM_TOWER,
search_config=EHC_CONFIG,
timeout=30
)
print(f"Succes: {result['success']}")
print(f"Temps: {result['time']:.2f}s")
if result['success']:
import re
cost_match = re.search(r'Plan cost:\s*(\d+)', result['stdout'])
if cost_match:
print(f"Cout du plan: {cost_match.group(1)}")
# Extraire la sequence d'actions
plan_match = re.search(r'Solution found!.*?Search time: ([\d.]+)s', result['stdout'], re.DOTALL)
if plan_match:
print(f"Temps de recherche: {plan_match.group(1)}s")=== Enforced Hill Climbing ===
Succes: False
Temps: 0.11s| Algorithme | Optimalite | Rapidite | Usage recommande |
|---|---|---|---|
| A* + blind | Oui | Lent | Problème simples, verification |
| A* + LM-cut | Oui | Moyen | Planification optimale |
| A* + FF | Non garanti | Rapide | Solutions de bonne qualite |
| Eager Greedy | Non | Très rapide | Solutions rapides |
| Lazy Greedy | Non | Très rapide | Grands problemes |
| EHC | Non | Variable | Problemes faciles |
Fast Downward implemente de nombreuses heuristiques. Voici les principales :
| Heuristique | Admissible | Type | Description |
|---|---|---|---|
| blind() | Oui | Triviale | Retourne 0 partout (BFS) |
| hmax() | Oui | Relaxation | Maximum des couts de sous-buts |
| lmcut() | Oui | Landmarks | Coupe de landmarks |
| ff() | Non | Relaxation | Fast Forward heuristic |
| add() | Non | Relaxation | Heuristique additive |
| cg() | Non | Causal | Graphe causal |
| cea() | Non | Contexte | Context-enhanced additive |
| merge_and_shrink() | Oui | Abstraction | Merge-and-shrink |
Le choix de l’algorithme de recherche (A*, Greedy, EHC) determine la stratégie d’exploration. Mais la qualite du guidage depend surtout de l’heuristique – la fonction qui estime la distance au but. Fast Downward propose une bibliotheque riche d’heuristiques, chacune avec des compromis entre precision, temps de calcul et admissibilite. La section suivante les classe et les compare systematiquement.
# Comparaison detaillee des heuristiques
HEURISTICS = [
("blind", "astar(blind())"),
("hmax", "astar(hmax())"),
("lmcut", "astar(lmcut())"),
("ff", "astar(ff())"),
("add", "astar(add())"),
]
if DOCKER_OK and FD_DOCKER_OK:
print("=== Comparaison des heuristiques (A*) ===")
print(f"{'Heuristique':<15} {'Succes':<10} {'Temps':<10} {'Cout':<10} {'Noeuds'}")
print("-" * 55)
import re
for name, config in HEURISTICS:
result = run_fast_downward_docker(
DOMAIN_BLOCKS, PROBLEM_TOWER,
search_config=config,
timeout=30
)
success_str = "OK" if result['success'] else "ECHEC"
time_str = f"{result['time']:.2f}s"
if result['success']:
cost_match = re.search(r'Plan cost:\s*(\d+)', result['stdout'])
nodes_match = re.search(r'Evaluated (\d+) state', result['stdout'])
cost = cost_match.group(1) if cost_match else "?"
nodes = nodes_match.group(1) if nodes_match else "?"
else:
cost = "-"
nodes = "-"
print(f"{name:<15} {success_str:<10} {time_str:<10} {cost:<10} {nodes}")=== Comparaison des heuristiques (A*) ===
Heuristique Succes Temps Cout Noeuds
-------------------------------------------------------
blind OK 0.13s 4 21
hmax OK 0.12s 4 13
lmcut OK 0.11s 4 10
ff OK 0.12s 4 11
add OK 0.12s 4 11Points cles :
blind() : Explore tous les etats jusqu’a trouver le but (equivalent BFS). Très lent mais toujours optimal.
hmax() : Heuristique admissible simple. Rapide mais estime souvent trop bas.
lmcut() : Meilleure heuristique admissible. Equilibre entre precision et temps de calcul.
ff() : Heuristique non admissible mais très precise. Souvent utilise avec Greedy.
add() : Relaxation additive. Peut surestimer le cout (non admissible).
Note : Pour un problème simple comme Blocks World, les différences sont minimes. L’impact des heuristiques devient evident sur des problemes plus complexes.
Le domaine Logistics est un classique de la planification. Il implique le transport de colis entre lieux avec des vehicules.
Après avoir etudie l’architecture, les algorithmes et les heuristiques de Fast Downward de maniere théorique, passons a un domaine concret. Le domaine Logistics est un classique des competitions de planification : il modelise le transport de colis entre lieux avec des vehicules, un problème directement applicable a la logistique reelle.
# Domaine Logistics simplifie
DOMAIN_LOGISTICS = """
(define (domain logistics)
(:requirements :strips :typing)
(:types location vehicle package)
(:predicates
(at ?p - package ?l - location)
(at-vehicle ?v - vehicle ?l - location)
(in ?p - package ?v - vehicle)
(connected ?from ?to - location)
)
(:action drive
:parameters (?v - vehicle ?from ?to - location)
:precondition (and (at-vehicle ?v ?from) (connected ?from ?to))
:effect (and (not (at-vehicle ?v ?from)) (at-vehicle ?v ?to))
)
(:action load
:parameters (?p - package ?v - vehicle ?l - location)
:precondition (and (at ?p ?l) (at-vehicle ?v ?l))
:effect (and (not (at ?p ?l)) (in ?p ?v))
)
(:action unload
:parameters (?p - package ?v - vehicle ?l - location)
:precondition (and (in ?p ?v) (at-vehicle ?v ?l))
:effect (and (not (in ?p ?v)) (at ?p ?l))
)
)
"""
# Probleme: transporter un colis de A vers C via B
PROBLEM_LOGISTICS = """
(define (problem logistics-simple)
(:domain logistics)
(:objects
loc-a loc-b loc-c - location
truck - vehicle
pkg1 - package
)
(:init
(at pkg1 loc-a)
(at-vehicle truck loc-a)
(connected loc-a loc-b)
(connected loc-b loc-c)
(connected loc-c loc-b)
(connected loc-b loc-a)
)
(:goal (at pkg1 loc-c))
)
"""
print("Domaine Logistics defini")
print("Probleme: transporter pkg1 de loc-a vers loc-c")Domaine Logistics defini
Probleme: transporter pkg1 de loc-a vers loc-cLancement de Fast Downward sur le domaine Logistics et affichage du plan optimal trouve, incluant les actions de chargement, transport et dechargement des colis.
# Resolution du probleme Logistics
if DOCKER_OK and FD_DOCKER_OK:
print("=== Resolution du probleme Logistics ===")
result = run_fast_downward_docker(
DOMAIN_LOGISTICS, PROBLEM_LOGISTICS,
search_config="astar(lmcut())",
timeout=30
)
print(f"Succes: {result['success']}")
print(f"Temps: {result['time']:.2f}s")
if result['success']:
import re
cost_match = re.search(r'Plan cost:\s*(\d+)', result['stdout'])
if cost_match:
print(f"Cout du plan: {cost_match.group(1)} actions")
# Afficher la sequence d'actions
print("\n--- Actions du plan ---")
lines = result['stdout'].split('\n')
in_plan = False
for line in lines:
if 'Solution found!' in line:
in_plan = True
if in_plan:
print(line)=== Resolution du probleme Logistics ===
Succes: True
Temps: 0.11s
Cout du plan: 4 actions
--- Actions du plan ---
[t=0.001617s, 10692 KB] Solution found!
[t=0.001625s, 10692 KB] Actual search time: 0.000129s
load pkg1 truck loc-a (1)
drive truck loc-a loc-b (1)
drive truck loc-b loc-c (1)
unload pkg1 truck loc-c (1)
[t=0.001634s, 10692 KB] Plan length: 4 step(s).
[t=0.001634s, 10692 KB] Plan cost: 4
[t=0.001634s, 10692 KB] Expanded 5 state(s).
[t=0.001634s, 10692 KB] Reopened 0 state(s).
[t=0.001634s, 10692 KB] Evaluated 7 state(s).
[t=0.001634s, 10692 KB] Evaluations: 7
[t=0.001634s, 10692 KB] Generated 9 state(s).
[t=0.001634s, 10692 KB] Dead ends: 0 state(s).
[t=0.001634s, 10692 KB] Expanded until last jump: 0 state(s).
[t=0.001634s, 10692 KB] Reopened until last jump: 0 state(s).
[t=0.001634s, 10692 KB] Evaluated until last jump: 1 state(s).
[t=0.001634s, 10692 KB] Generated until last jump: 0 state(s).
[t=0.001634s, 10692 KB] Number of registered states: 7
[t=0.001634s, 10692 KB] Int hash set load factor: 7/8 = 0.875000
[t=0.001634s, 10692 KB] Int hash set resizes: 3
[t=0.001634s, 10692 KB] Search time: 0.000215s
[t=0.001634s, 10692 KB] Total time: 0.001634s
Solution found.
Peak memory: 10692 KB
Remove intermediate file output.sas
search exit code: 0
INFO Planner time: 0.08s
Le plan attendu devrait contenir les actions suivantes :
| Étape | Action | Effet |
|---|---|---|
| 1 | load(pkg1, truck, loc-a) |
Colis dans le camion |
| 2 | drive(truck, loc-a, loc-b) |
Camion en B |
| 3 | drive(truck, loc-b, loc-c) |
Camion en C |
| 4 | unload(pkg1, truck, loc-c) |
Colis en C |
Cout total : 4 actions
La bibliotheque unified-planning offre une interface Python unifiee pour interagir avec Fast Downward.
# Utilisation de unified-planning avec Fast Downward
if UP_OK:
from unified_planning.shortcuts import *
from up_fast_downward import FastDownwardPDDLPlanner
from unified_planning.engines import PlanGenerationResultStatus, CompilationKind
from collections import OrderedDict
# Definir le probleme Blocks World avec unified-planning
Block = UserType('Block')
# IMPORTANT: unified-planning 1.3+ require OrderedDict for Fluent signatures
on = Fluent('on', BoolType(), OrderedDict([('x', Block), ('y', Block)]))
ontable = Fluent('ontable', BoolType(), OrderedDict([('x', Block)]))
clear = Fluent('clear', BoolType(), OrderedDict([('x', Block)]))
handempty = Fluent('handempty', BoolType())
holding = Fluent('holding', BoolType(), OrderedDict([('x', Block)]))
problem = Problem('blocks-up')
# Objets
a = Object('a', Block)
b = Object('b', Block)
c = Object('c', Block)
problem.add_objects([a, b, c])
# Etat initial
problem.set_initial_value(ontable(a), True)
problem.set_initial_value(ontable(b), True)
problem.set_initial_value(ontable(c), True)
problem.set_initial_value(clear(a), True)
problem.set_initial_value(clear(b), True)
problem.set_initial_value(clear(c), True)
problem.set_initial_value(handempty, True)
# But
problem.add_goal(on(a, b))
problem.add_goal(on(b, c))
# Actions - IMPORTANT: use OrderedDict for parameters
pick_up = InstantaneousAction('pick-up', OrderedDict([('x', Block)]))
# Get the action's own parameter
x_pick = pick_up.parameter('x')
pick_up.add_precondition(clear(x_pick))
pick_up.add_precondition(ontable(x_pick))
pick_up.add_precondition(handempty)
pick_up.add_effect(ontable(x_pick), False)
pick_up.add_effect(clear(x_pick), False)
pick_up.add_effect(handempty, False)
pick_up.add_effect(holding(x_pick), True)
problem.add_action(pick_up)
put_down = InstantaneousAction('put-down', OrderedDict([('x', Block)]))
x_put = put_down.parameter('x')
put_down.add_precondition(holding(x_put))
put_down.add_effect(holding(x_put), False)
put_down.add_effect(clear(x_put), True)
put_down.add_effect(handempty, True)
put_down.add_effect(ontable(x_put), True)
problem.add_action(put_down)
stack = InstantaneousAction('stack', OrderedDict([('x', Block), ('y', Block)]))
x_stack = stack.parameter('x')
y_stack = stack.parameter('y')
stack.add_precondition(holding(x_stack))
stack.add_precondition(clear(y_stack))
stack.add_effect(holding(x_stack), False)
stack.add_effect(clear(y_stack), False)
stack.add_effect(clear(x_stack), True)
stack.add_effect(handempty, True)
stack.add_effect(on(x_stack, y_stack), True)
problem.add_action(stack)
print("Probleme unified-planning defini")
# IMPORTANT: Use problem.all_objects (list) instead of problem.objects() (method)
print(f"Objets: {[o.name for o in problem.all_objects]}")
print(f"Actions: {[a.name for a in problem.actions]}")
else:
print("unified-planning non disponible")Probleme unified-planning defini
Objets: ['a', 'b', 'c']
Actions: ['pick-up', 'put-down', 'stack']Résultat obtenu : Le problème Blocks World est traduit en objets Python types (Block), predicats (Fluent), et actions (InstantaneousAction).
| Concept PDDL | Equivalent unified-planning | Exemple |
|---|---|---|
(:types block) |
UserType('Block') |
Type abstrait |
(:predicates (on ?x ?y)) |
Fluent('on', BoolType(), ...) |
Predicat booléen |
(:objects a b c) |
Object('a', Block) |
Instance |
(:init ...) |
problem.set_initial_value(...) |
Etat initial |
(:goal ...) |
problem.add_goal(...) |
But |
(:action pick-up ...) |
InstantaneousAction('pick-up', ...) |
Opérateur |
Note technique : unified-planning 1.3+ impose OrderedDict pour les paramètres des Fluent et InstantaneousAction, afin de garantir un ordre déterministe lors de la traduction vers PDDL.
Resolution du même problème via l’interface unified-planning en testant les planificateurs disponibles et en comparant leurs résultats avec l’appel Docker direct.
# Resolution avec unified-planning - Test des planificateurs disponibles
if UP_OK:
from unified_planning.shortcuts import OneshotPlanner
from unified_planning.engines import PlanGenerationResultStatus
# Afficher les planificateurs disponibles
print("Test de resolution avec unified-planning...")
print("=" * 50)
# Essayer Fast Downward
try:
from up_fast_downward import FastDownwardPDDLPlanner
print("1. Test avec Fast Downward...")
planner_fd = FastDownwardPDDLPlanner()
result_fd = planner_fd.solve(problem)
print(f" Statut: {result_fd.status}")
if result_fd.status == PlanGenerationResultStatus.SOLVED_SATISFICING:
print(f" Plan trouve: {len(result_fd.plan.actions)} actions")
except Exception as e:
print(f" Erreur: Fast Downward non installe localement")
print(f" Detail: {str(e)[:100]}")
# Essayer Pyperplan (planificateur Python pur)
try:
print("\n2. Test avec Pyperplan...")
with OneshotPlanner(name='pyperplan') as planner:
result = planner.solve(problem)
if result.status in (PlanGenerationResultStatus.SOLVED_SATISFICING,
PlanGenerationResultStatus.SOLVED_OPTIMALLY):
print(f" Statut: {result.status}")
print(f"\n Solution trouvee !")
print(" " + "=" * 40)
for i, action in enumerate(result.plan.actions):
params = ', '.join(str(p) for p in action.actual_parameters)
print(f" {i+1}. {action.action.name}({params})")
print(" " + "=" * 40)
print(f" Longueur du plan: {len(result.plan.actions)} actions")
# Analyse du plan
print(f"\n Analyse du plan:")
print(f" - Actions pick-up: {sum(1 for a in result.plan.actions if a.action.name == 'pick-up')}")
print(f" - Actions put-down: {sum(1 for a in result.plan.actions if a.action.name == 'put-down')}")
print(f" - Actions stack: {sum(1 for a in result.plan.actions if a.action.name == 'stack')}")
else:
print(f" Statut: {result.status}")
except ImportError:
print(" Pyperplan non installe. Installez-le avec: pip install up-pyperplan")
except Exception as e:
print(f" Erreur: {e}")
# Si aucun planificateur n'a fonctionne, afficher un exemple
print("\n" + "=" * 50)
print("NOTE: Pour utiliser Fast Downward, installez-le localement:")
print(" https://www.fast-downward.org/")
print("\nAlternatives Python:")
print(" pip install up-pyperplan # Planificateur Python pur")
print(" pip install up-tamer # Planificateur base sur des heuristiques")
else:
print("Resolution impossible sans unified-planning")Test de resolution avec unified-planning...
==================================================
1. Test avec Fast Downward...
Statut: PlanGenerationResultStatus.INTERNAL_ERROR
2. Test avec Pyperplan...
Erreur:
==================================================
NOTE: Pour utiliser Fast Downward, installez-le localement:
https://www.fast-downward.org/
Alternatives Python:
pip install up-pyperplan # Planificateur Python pur
pip install up-tamer # Planificateur base sur des heuristiquesRésultat obtenu : L’interface Python unified-planning tente plusieurs planificateurs. Fast Downward retourne une erreur interne (installation locale incomplete), et Pyperplan echoue également.
| Planificateur | Statut | Cause probable |
|---|---|---|
| Fast Downward | INTERNAL_ERROR |
Binaire non trouve dans le PATH |
| Pyperplan | Erreur silencieuse | Plugin non installe (pip install up-pyperplan) |
Points cles : - unified-planning normalise les statuts de résultat (SOLVED_SATISFICING, SOLVED_OPTIMALLY, INTERNAL_ERROR) - L’avantage de cette interface est de pouvoir tester plusieurs moteurs sans modifier le code du problème - En cas d’indisponibilite des planificateurs, la definition du problème reste valide et peut etre exportee en PDDL pour exécution manuelle - Pour un environnement fonctionnel, il faut installer Fast Downward localement ET le plugin Python up-fast-downward
| Concept | Description |
|---|---|
| Translator | Convertit PDDL en SAS+ (encodage compact) |
| Preprocessor | Simplifie et normalise la tâche |
| Search | Algorithme de recherche (A*, Greedy, EHC) |
| Heuristique | Estime le cout vers le but |
| Admissible | Ne surestime jamais (optimalite garantie) |
| Objectif | Algorithme recommande |
|---|---|
| Solution optimale | astar(lmcut()) |
| Solution rapide | lazy_greedy([ff()]) |
| Verifier l’optimalite | astar(blind()) (reference) |
| Problemes faciles | ehc([ff()]) |
| Grands problemes | lazy_greedy([ff(), cea()]) |
Fast Downward permet de specifier des limites :
Nous modelisons un problème de Ferry ou un bateau transporte des voitures entre deux rives d’un fleuve. Le ferry a une capacite de 1 voiture a la fois. Ce problème illustre un workflow complet : analyse du problème, modelisation PDDL, choix d’algorithme, exécution et interpretation.
Scénario : 3 voitures (car1, car2, car3) sont sur la rive gauche et doivent toutes etre transportees sur la rive droite. Le ferry commence sur la rive gauche.
# Exemple guide 1 : Probleme Ferry — Workflow complet
# Domaine PDDL : transport de voitures par ferry
DOMAIN_FERRY = """
(define (domain ferry)
(:requirements :strips :typing)
(:types car location)
(:predicates
(car-on-ferry ?c - car)
(car-at ?c - car ?l - location)
(ferry-at ?l - location)
(empty-ferry)
)
(:action board
:parameters (?c - car ?l - location)
:precondition (and (car-at ?c ?l) (ferry-at ?l) (empty-ferry))
:effect (and (not (car-at ?c ?l)) (car-on-ferry ?c) (not (empty-ferry)))
)
(:action sail
:parameters (?from ?to - location)
:precondition (ferry-at ?from)
:effect (and (not (ferry-at ?from)) (ferry-at ?to))
)
(:action debark
:parameters (?c - car ?l - location)
:precondition (and (car-on-ferry ?c) (ferry-at ?l))
:effect (and (not (car-on-ferry ?c)) (car-at ?c ?l) (empty-ferry))
)
)
"""
# Probleme : 3 voitures a transporter de la rive gauche vers la rive droite
PROBLEM_FERRY = """
(define (problem ferry-3cars)
(:domain ferry)
(:objects car1 car2 car3 - car left right - location)
(:init
(ferry-at left)
(empty-ferry)
(car-at car1 left)
(car-at car2 left)
(car-at car3 left)
)
(:goal (and (car-at car1 right) (car-at car2 right) (car-at car3 right)))
)
"""
print("Domaine Ferry defini")
print("Actions: board(car, location), sail(from, to), debark(car, location)")
print("Probleme: 3 voitures a transporter de gauche a droite")
print()
# Choix strategique de l'algorithme :
# - A* + lmcut (admissible) pour garantir l'optimalite
# - Puis GBFS + FF pour comparer la rapidite
print("=" * 60)
print("1. Resolution OPTIMALE : A* + LM-cut")
print("=" * 60)
if DOCKER_OK and FD_DOCKER_OK:
import re
# Resolution optimale
result_optimal = run_fast_downward_docker(
DOMAIN_FERRY, PROBLEM_FERRY,
search_config="astar(lmcut())",
timeout=30
)
if result_optimal['success']:
print(f"Succes: {result_optimal['success']}")
print(f"Temps: {result_optimal['time']:.2f}s")
cost_match = re.search(r'Plan cost:\s*(\d+)', result_optimal['stdout'])
nodes_match = re.search(r'Evaluated (\d+) state', result_optimal['stdout'])
if cost_match:
print(f"Cout optimal: {cost_match.group(1)} actions")
if nodes_match:
print(f"Noeuds evalues: {nodes_match.group(1)}")
# Extraire les actions du plan
print("\nPlan optimal :")
plan_lines = []
for line in result_optimal['stdout'].split('\n'):
line = line.strip()
if line and not line.startswith('[') and '(' in line and ')' in line:
if any(cmd in line for cmd in ['board', 'sail', 'debark', 'load', 'unload', 'drive']):
plan_lines.append(line)
for i, action in enumerate(plan_lines, 1):
print(f" {i}. {action}")
else:
print(f"Erreur: {result_optimal.get('error', 'Inconnue')}")
print()
print("=" * 60)
print("2. Resolution RAPIDE : Greedy + FF (satisficing)")
print("=" * 60)
# Resolution satisficing
result_greedy = run_fast_downward_docker(
DOMAIN_FERRY, PROBLEM_FERRY,
search_config="eager_greedy([ff()])",
timeout=30
)
if result_greedy['success']:
print(f"Succes: {result_greedy['success']}")
print(f"Temps: {result_greedy['time']:.2f}s")
cost_match = re.search(r'Plan cost:\s*(\d+)', result_greedy['stdout'])
nodes_match = re.search(r'Evaluated (\d+) state', result_greedy['stdout'])
if cost_match:
print(f"Cout du plan: {cost_match.group(1)} actions")
if nodes_match:
print(f"Noeuds evalues: {nodes_match.group(1)}")
else:
print(f"Erreur: {result_greedy.get('error', 'Inconnue')}")
# Comparaison
print()
print("=" * 60)
print("3. Comparaison des strategies")
print("=" * 60)
print(f"{'Strategie':<25} {'Optimal?':<10} {'Temps':<10} {'Noeuds'}")
print("-" * 55)
if result_optimal['success']:
cost_o = re.search(r'Plan cost:\s*(\d+)', result_optimal['stdout'])
nodes_o = re.search(r'Evaluated (\d+) state', result_optimal['stdout'])
print(f"{'A* + LM-cut (optimal)':<25} {'Oui':<10} {result_optimal['time']:.2f}s {nodes_o.group(1) if nodes_o else '?'}")
if result_greedy['success']:
cost_g = re.search(r'Plan cost:\s*(\d+)', result_greedy['stdout'])
nodes_g = re.search(r'Evaluated (\d+) state', result_greedy['stdout'])
is_opt = "Oui" if cost_o and cost_g and cost_o.group(1) == cost_g.group(1) else "Non"
print(f"{'Greedy + FF (rapide)':<25} {is_opt:<10} {result_greedy['time']:.2f}s {nodes_g.group(1) if nodes_g else '?'}")
print()
print("Plan attendu (optimal, 11 actions) :")
print(" board(car1, left) -> sail(left, right) -> debark(car1, right)")
print(" -> sail(right, left) -> board(car2, left) -> sail(left, right)")
print(" -> debark(car2, right) -> sail(right, left) -> board(car3, left)")
print(" -> sail(left, right) -> debark(car3, right)")
else:
print("Docker/Fast Downward non disponible — plan attendu :")
print(" 11 actions (3x board, 3x sail right, 3x debark, 2x sail back)")
print(" Cycle : board -> sail(L->R) -> debark -> sail(R->L) pour chaque voiture")
print(" Sauf la derniere ou le retour est inutile -> 3*3 + 2 = 11 actions")Domaine Ferry defini
Actions: board(car, location), sail(from, to), debark(car, location)
Probleme: 3 voitures a transporter de gauche a droite
============================================================
1. Resolution OPTIMALE : A* + LM-cut
============================================================
Succes: True
Temps: 0.12s
Cout optimal: 11 actions
Noeuds evalues: 35
Plan optimal :
1. board car1 left (1)
2. sail left right (1)
3. debark car1 right (1)
4. sail right left (1)
5. board car2 left (1)
6. sail left right (1)
7. debark car2 right (1)
8. sail right left (1)
9. board car3 left (1)
10. sail left right (1)
11. debark car3 right (1)
============================================================
2. Resolution RAPIDE : Greedy + FF (satisficing)
============================================================
Succes: True
Temps: 0.11s
Cout du plan: 11 actions
Noeuds evalues: 17
============================================================
3. Comparaison des strategies
============================================================
Strategie Optimal? Temps Noeuds
-------------------------------------------------------
A* + LM-cut (optimal) Oui 0.12s 35
Greedy + FF (rapide) Oui 0.11s 17
Plan attendu (optimal, 11 actions) :
board(car1, left) -> sail(left, right) -> debark(car1, right)
-> sail(right, left) -> board(car2, left) -> sail(left, right)
-> debark(car2, right) -> sail(right, left) -> board(car3, left)
-> sail(left, right) -> debark(car3, right)Ce problème Ferry illustre le workflow complet de planification automatique :
Étape 1 — Analyse du problème : 3 voitures, 2 rives, ferry capacite 1. Le plan optimal necessite un cycle board -> sail -> debark -> sail par voiture, sauf la dernière ou le retour est inutile. Cout théorique : 3*3 + 2 = 11 actions.
Étape 2 — Modelisation PDDL : 3 actions (board, sail, debark) avec des preconditions qui garantissent la coherence (ferry present, voiture disponible, ferry vide pour boarder).
Étape 3 — Choix de l’algorithme : - A* + LM-cut garantit l’optimalite mais evalue plus d’etats - Greedy + FF trouve une solution rapidement mais ne garantit pas l’optimalite
Étape 4 — Résultats : Sur ce problème, Greedy+FF peut trouver la même solution optimale qu’A*+LM-cut car le domaine est simple. La différence devient marquee sur des problemes avec plus de voitures ou des contraintes additionnelles.
Generalisation : Pour n voitures sur 2 rives avec capacite 1, le plan optimal contient 3n + (n-1) = 4n - 1 actions (n cycles board-sail-debark + n-1 retours).
Modifiez le problème Blocks World pour avoir 4 blocs (A, B, C, D) avec le but de construire une tour A-B-C-D. Comparez les temps de resolution de blind(), hmax(), lmcut() et ff().
# Exercice 1 : Comparaison avec 4 blocs
# Exercice: Definissez le probleme PDDL pour 4 blocs (A, B, C, D)
# But: construire la tour A-B-C-D (on(a,b), on(b,c), on(c,d))
#
# Indice: Repartez du format PROBLEM_TOWER (cellule precedente)
# en ajoutant un bloc 'd' dans :objects et :init
# PROBLEM_4BLOCKS = """
# (define (problem blocks-4)
# (:domain blocks)
# (:objects ... )
# (:init ... )
# (:goal (and ... ))
# )
# """
# Exercice: Testez les 4 heuristiques et comparez les resultats
#
# Heuristiques a comparer: blind(), hmax(), lmcut(), ff()
#
# Pour chaque heuristique:
# 1. Appeler run_fast_downward_docker(DOMAIN_BLOCKS, PROBLEM_4BLOCKS, search_config=...)
# 2. Mesurer le temps (result['time'])
# 3. Extraire le cout du plan (re.search(r'Plan cost:\s*(\d+)', result['stdout']))
# 4. Extraire le nombre de noeuds evalues
#
# Indice: Reutilisez le pattern de la cellule 18 (SEARCH_CONFIGS)
# Indice: Les heuristiques admissibles (blind, hmax, lmcut) doivent donner le meme cout
pass # Remplacer par votre implementation
print("Exercice a completer")Exercice a completerIndice : Repartez du problème PROBLEM_TOWER en ajoutant un bloc d dans :objects et :init. Le but devient (and (on a b) (on b c) (on c d)). Les heuristiques admissibles (blind, hmax, lmcut) doivent toutes trouver le même cout optimal. Observez comment le nombre de noeuds expanses varie selon la qualite du guidage heuristique.
Le domaine Gripper implique un robot avec deux pinces qui doit deplacer des balles entre deux pieces. Implementez le domaine et testez-le avec Fast Downward.
Exercice a completerIndice : Le domaine Gripper comporte trois types d’actions : pick(ball, room, gripper) pour saisir une balle, drop(ball, room, gripper) pour la poser, et move(room1, room2) pour deplacer le robot. Chaque gripper peut tenir au plus une balle a la fois. Definez les types room, ball, gripper et les predicats at-robot, at-ball, carrying, free dans la declaration du domaine PDDL.
Pour un problème donne, trouvez la configuration (algorithme + heuristique) qui minimise le temps de resolution tout en garantissant l’optimalite.
Exercice a completerIndice : Une heuristique admissible garantit l’optimalite du plan trouve. Parmi les heuristiques testees, seules blind(), hmax() et lmcut() sont admissibles. Utilisez time.time() pour mesurer le temps de chaque appel et re.search(r'Evaluated (\d+) state', ...) pour extraire le nombre de noeuds expanses. La configuration optimale est celle qui minimise le produit temps x noeuds tout en garantissant le même cout de plan.
Dans ce notebook, vous avez appris :
Dans le notebook Planners-5-Heuristics, nous approfondirons la théorie des heuristiques : - Construction de relaxation - Heuristiques additives vs max - Landmarks et LM-cut - Pattern Databases
Notebook suivant : Planners-5-Heuristics