Navigation : Index | << Setup | PDDL Basics >>
A la fin de ce notebook, vous saurez :
La planification automatique est une branche fondamentale de l’intelligence artificielle qui s’interesse a la generation autonome de sequences d’actions pour atteindre un objectif.
Planification : Processus de determination d’une sequence d’actions qui menera un agent d’un etat initial \(I\) vers un etat but \(G\), en respectant les contraintes du domaine \(D\).
Un problème de planification est formellement défini comme un triplet :
\[\mathcal{P} = \langle I, G, D \rangle\]
ou : - \(I\) : Etat initial du monde - \(G\) : Condition de but (etat ou ensemble d’etats cibles) - \(D\) : Théorie du domaine (actions disponibles, predicats, types)
La planification repose sur trois concepts fondamentaux :
| Concept | Description | Exemple (Robot) |
|---|---|---|
| Etat | Configuration du monde a un instant donne | Position du robot, objets portes |
| Action | Transition entre etats (preconditions + effets) | Se deplacer, prendre un objet |
| But | Condition a satisfaire | Livrer le colis a destination |
La resolution d’un problème de planification produit un plan :
\[\pi = \langle a_1, a_2, \ldots, a_n \rangle\]
Une sequence d’actions telle que l’exécution de \(\pi\) depuis \(I\) atteint \(G\).
Considerons un problème classique : un voyageur doit aller de Paris a Tokyo.
Etat initial: a(Paris) ^ billet(Paris, Tokyo)
Etat but: a(Tokyo)
Actions:
- prendre_avion(X, Y): precondition a(X) ^ billet(X, Y)
effet a(Y) ^ ¬a(X) ^ ¬billet(X, Y)Plan solution : [prendre_avion(Paris, Tokyo)]
Ce problème simple illustre la structure fondamentale de tout problème de planification.
STRIPS (Stanford Research Institute Problem Solver, 1971) est le modèle fondateur de la planification classique. Il définit un cadre formel pour representer les problemes de planification.
Le modèle STRIPS repose sur plusieurs hypotheses restrictives :
| Hypothese | Description | Consequence |
|---|---|---|
| Statique | L’environnement ne change que par les actions de l’agent | Pas d’événements externes |
| Déterministe | Chaque action a un effet unique et predictible | Pas d’incertitude sur les effets |
| Observable | L’agent connait parfaitement l’etat courant | Pas d’information cachee |
| Discret | Les etats et actions sont denombrables | Manipulation finie |
| Instantane | Les actions n’ont pas de duree | Pas de temporalite |
Ces hypotheses permettent d’utiliser des algorithmes de recherche classiques pour resoudre les problemes de planification.
Une action STRIPS est définie par quatre composantes :
\[a = \langle \text{name}, \text{params}, \text{precond}, \text{effects} \rangle\]
Action: pick-up(x)
Paramètres: ?x - Block
Preconditions: clear(x), ontable(x), handempty
Effets: holding(x), ¬ontable(x), ¬clear(x), ¬handemptyNotation : - Les preconditions sont des litteraux positifs qui doivent etre vrais - Les effets comprennent une liste additive (+) et une liste soustractive (-)
Dans le formalisme STRIPS, un etat est un ensemble de predicats (faits vrais). Une action \(a\) est applicable dans un etat \(s\) si :
\[\text{precond}(a) \subseteq s\]
L’application de \(a\) dans \(s\) produit un nouvel etat \(s'\) :
\[s' = (s \setminus \text{del}(a)) \cup \text{add}(a)\]
ou : - \(\text{del}(a)\) : effets negatifs (litteraux retires) - \(\text{add}(a)\) : effets positifs (litteraux ajoutes)
En planification automatique, on distingue deux niveaux de description :
Le domaine decrit les aspects generiques et reutilisables : - Les types d’objets (Block, Location, Robot…) - Les predicats (relations entre objets) - Les actions (schemas d’actions paramètres)
Le domaine est invariant : il peut etre reutilise pour différents problemes.
Le problème decrit une instance spécifique : - Les objets concrets (block_a, location_paris…) - L’etat initial (configuration de depart) - Le but (objectif a atteindre)
DOMAINE (generique) PROBLÈME (instance)
================== ===================
Types: Block Objets: a, b, c
Predicats: Etat initial:
on(?x, ?y) on(a, b), ontable(c)
clear(?x) clear(a), clear(c)
Actions: But:
pick-up(?x) on(b, a)
stack(?x, ?y)Cette separation permet de : - Reutiliser un domaine pour plusieurs problemes - Comparer différents planificateurs sur les mêmes instances - Structurer clairement la modelisation
Commencons par un exemple minimaliste : un interrupteur qui peut etre allume ou eteint.
Types : Switch (interrupteur)
Predicats : - on(s) : l’interrupteur s est allume - off(s) : l’interrupteur s est eteint
Actions : - turn_on(s) : allumer l’interrupteur - Preconditions : off(s) - Effets : on(s), not(off(s)) - turn_off(s) : eteindre l’interrupteur - Preconditions : on(s) - Effets : off(s), not(on(s))
Utilisons la bibliotheque unified-planning pour modeliser ce problème simple.
# 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 as e:
print(f"ERREUR: unified-planning non installe: {e}")
print("Executez le notebook Planners-0-Setup.ipynb pour l'installation.")
UP_OK = Falseunified-planning version: 1.3.0Modelisation du problème de l’interrupteur en utilisant l’API unified-planning avec un environnement explicite et des paramètres d’action typés.
# Modelisation du probleme de l'interrupteur
if UP_OK:
from unified_planning.environment import Environment
from collections import OrderedDict
# Pour unified-planning v1.3.0, nous devons utiliser l'API correcte
# Le probleme avec l'API originale est que UserType, Fluent, Variable
# doivent etre crees avec un environnement explicite
# Creation de l'environnement
env = Environment()
# Definition du type
Switch = env.type_manager.UserType('Switch')
# Definition des predicats (fluents) avec OrderedDict pour la signature
on_sig = OrderedDict([('sw', Switch)])
on = Fluent('on', BoolType(), _signature=on_sig, environment=env)
off_sig = OrderedDict([('sw', Switch)])
off = Fluent('off', BoolType(), _signature=off_sig, environment=env)
# Creation du probleme
problem = Problem('light-switch', env)
# Ajout d'un interrupteur (avec environnement explicite)
s = Object('s', Switch, environment=env)
problem.add_object(s)
# Definition des actions
# Pour les actions avec parametres, utiliser OrderedDict pour _parameters
params = OrderedDict([('sw', Switch)])
turn_on = InstantaneousAction('turn_on', _parameters=params, _env=env)
# Recuperer la variable depuis l'action
sw = turn_on.sw
turn_on.add_precondition(off(sw))
turn_on.add_effect(on(sw), True)
turn_on.add_effect(off(sw), False)
problem.add_action(turn_on)
turn_off = InstantaneousAction('turn_off', _parameters=params, _env=env)
sw = turn_off.sw
turn_off.add_precondition(on(sw))
turn_off.add_effect(off(sw), True)
turn_off.add_effect(on(sw), False)
problem.add_action(turn_off)
# Etat initial : interrupteur eteint
problem.set_initial_value(on(s), False)
problem.set_initial_value(off(s), True)
# But : interrupteur allume
problem.add_goal(on(s))
print("Probleme 'light-switch' cree")
print(f" Objets: {list(problem.objects(Switch))}")
print(f" Actions: {[a.name for a in problem.actions]}")
print(f" Etat initial: off(s)")
print(f" But: on(s)")Probleme 'light-switch' cree
Objets: [s]
Actions: ['turn_on', 'turn_off']
Etat initial: off(s)
But: on(s)Le code montre comment modéliser un problème de planification avec unified-planning.
Composantes créées :
| Élément | Description | Valeur |
|---|---|---|
| Type | Switch |
Type d’objet (interrupteur) |
| Fluents | on, off |
Prédicats booléens sur les interrupteurs |
| Objet | s |
Instance unique de type Switch |
| Actions | turn_on, turn_off |
Actions avec préconditions et effets |
| État initial | off(s)=True, on(s)=False |
Interrupteur éteint au départ |
| But | on(s)=True |
Interrupteur allumé à la fin |
Points clés de l’API unified-planning : 1. Environment : Espace de noms pour éviter les conflits de noms 2. UserType : Définit des types d’objets personnalisés 3. Fluent : Prédicat dont la valeur peut changer (état dynamique) 4. InstantaneousAction : Action instantanée avec préconditions et effets 5. OrderedDict : Nécessaire pour les signatures de paramètres (bug v1.3.0)
Remarque sur la structure : - Les préconditions utilisent add_precondition() - Les effets utilisent add_effect(fluent, valeur) - Les effets négatifs sont gérés en mettant le fluent à False
Note pédagogique : Ce pattern de modélisation (type → fluents → actions → état → but) est réutilisable pour tous les problèmes de planification classique.
# Resolution avec un planificateur
if UP_OK:
from unified_planning.engines import PlanGenerationResultStatus
# Desactiver les messages de credits pour plus de clarte
from unified_planning.shortcuts import get_environment
get_environment().credits_stream = None
# Utiliser OneshotPlanner avec pyperplan (planificateur pur Python)
# Fast Downward est disponible mais peut avoir des problemes de configuration
try:
print("Utilisation du planificateur: pyperplan")
print("\nResolution en cours...")
# OneshotPlanner est un context manager
with OneshotPlanner(name='pyperplan') as planner:
result = planner.solve(problem)
if result.status == PlanGenerationResultStatus.SOLVED_SATISFICING:
print("\nSolution trouvee !")
print("=" * 40)
for i, action in enumerate(result.plan.actions):
# Format different pour pyperplan
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)} action(s)")
else:
print(f"Statut: {result.status}")
if result.log_messages:
print("Messages:", result.log_messages)
except Exception as e:
print(f"Erreur lors de la resolution: {e}")
print("\nNote: Assurez-vous que 'up-pyperplan' est installe:")
print(" pip install 'unified-planning[pyperplan]'")Utilisation du planificateur: pyperplan
Resolution en cours...
Solution trouvee !
========================================
1. turn_on(s)
========================================
Longueur du plan: 1 action(s)La resolution ci-dessus a fonctionne parce que deux briques distinctes etaient presentes. C’est un point structurant de la planification automatique.
| Composant | Rôle | Statut ici |
|---|---|---|
unified-planning |
Bibliotheque de modelisation (types, fluents, actions, but) | Installe (v1.3.0) |
pyperplan |
Planificateur effectif (recherche le plan) | Installe, utilise ci-dessus |
| Fast Downward | Planificateur C++ performant (alternative) | Disponible |
Pourquoi deux couches ? - unified-planning est une interface : elle decrit le problème mais ne le resout pas. - Le calcul du plan est delegue a un planificateur branche via OneshotPlanner(name=...). - Si aucun planificateur n’est installe, unified-planning leve une erreur – on installe alors la dépendance :
Point cle pedagogique : La planification automatique necessite deux couches : (1) une bibliotheque de modelisation (unified-planning, PDDL) et (2) un planificateur effectif (pyperplan, Fast Downward, LAMA). C’est analogue a avoir une bibliotheque d’algebre lineaire (NumPy) et un solveur (scipy.linalg.solve).
Note : Les notebooks suivants utilisent aussi Fast Downward, plus robuste et performant sur les gros problemes.
Le planificateur trouve la solution attendue :
| Étape | Action | Etat resultant |
|---|---|---|
| Initial | - | off(s) |
| 1 | turn_on(s) |
on(s) |
Observations : - Le problème est trivial mais illustre le processus de planification - L’action turn_on est la seule applicable dans l’etat initial - Le plan ne contient qu’une seule action (optimal)
Note : Ce problème simple montre le flux complet : modelisation -> resolution -> plan.
La planification classique STRIPS est le point de depart, mais il existe de nombreuses extensions pour des scénarios plus complexes.
| Paradigme | Extensions | Applications typiques |
|---|---|---|
| Classique | STRIPS, PDDL | Casse-tetes, logistique |
| Numérique | Variables continues | Gestion de ressources |
| Temporelle | Duree, parallelisme | Ordonnancement, planification de projets |
| Hiérarchique (HTN) | Méthodes, tâches abstraites | Planification stratégique |
| Probabiliste (MDP/POMDP) | Incertitude, observations partielles | Robotique, dialogue |
| Multi-agents | Agents cooperatifs/competitifs | Jeux, negociation |
Planification classique : - Hypotheses STRIPS (déterministe, observable, statique) - Recherche dans un graphe d’etats - Heuristiques admissibles pour l’optimalite
Extensions principales :
La planification classique STRIPS est le point de départ, mais il existe de nombreuses extensions pour des scénarios plus complexes.
| Paradigme | Extensions | Applications typiques |
|---|---|---|
| Classique | STRIPS, PDDL | Casse-têtes, logistique |
| Numérique | Variables continues | Gestion de ressources |
| Temporelle | Durée, parallélisme | Ordonnancement, planification de projets |
| Hiérarchique (HTN) | Méthodes, tâches abstraites | Planification stratégique |
| Probabiliste (MDP/POMDP) | Incertitude, observations partielles | Robotique, dialogue |
| Multi-agents | Agents coopératifs/compétitifs | Jeux, négociation |
Note pédagogique : Ce notebook couvre la planification classique STRIPS. Les paradigmes temporel, HTN et neuro-symbolique seront abordés dans les notebooks suivants de cette série.
graph TD
A[Planification] --> B[Classique]
A --> C[Temporelle]
A --> D[Numérique]
A --> E[Hiérarchique]
A --> F[Probabiliste]
A --> G[Multi-agents]
B --> B1[STRIPS]
B --> B2[PDDL]
C --> C1[Durations]
C --> C2[Parallelisme]
D --> D1[Ressources]
D --> D2[Continu]
E --> E1[HTN]
E --> E2[Méthodes]
F --> F1[MDP]
F --> F2[POMDP]
G --> G1[Cooperatif]
G --> G2[Competitif]La planification automatique a une riche histoire dans le domaine de l’IA.
| Periode | Développement | Impact |
|---|---|---|
| 1969-1971 | STRIPS (Fikes & Nilsson) | Modèle fondateur |
| 1971-1975 | NOAH, NONLIN | Planification non-lineaire |
| 1990s | Graphplan, SATPlan | Algorithmes efficaces |
| 1998 | PDDL standardise | Langage commun pour IPC |
| 2000s | LAMA, Fast Downward | Heuristiques puissantes |
| 2010s | Integration RL/Neural | Planification neuro-symbolique |
| 2020s | LLM + Planning | Planification avec modèles de langage |
L’IPC est organise tous les 2-3 ans depuis 1998. Elle a joue un rôle majeur dans l’avancement de la planification :
| Outil | Type | Particularite |
|---|---|---|
| Fast Downward | Optimal/Satisficing | Heuristiques LM-cut, FF |
| LAMA | Portfolio | Gagnant IPC multiple |
| unified-planning | Bibliotheque Python | Interface unifiee |
| OR-Tools CP-SAT | Programmation par contraintes | Planification + optimisation |
La planification peut etre vue comme une recherche dans un graphe d’etats.
Un problème de planification définit implicitement un graphe :
Le nombre d’etats peut croitre de maniere exponentielle :
\[|S| = O(2^n)\]
ou \(n\) est le nombre de predicats (faits) possibles.
Exemple : Pour un problème avec 50 predicats binaires : - Nombre d’etats possibles : \(2^{50} \approx 10^{15}\) - Exploration exhaustive impossible
C’est pourquoi les heuristiques sont essentielles pour guider la recherche.
# Illustration de l'explosion combinatoire
import math
def estimate_states(num_predicates):
"""Estime le nombre d'etats possibles pour n predicats."""
return 2 ** num_predicates
print("Explosion combinatoire du nombre d'etats")
print("=" * 50)
print(f"{'Predicats':<12} {'Etats possibles':<20} {'Ordre de grandeur'}")
print("-" * 50)
for n in [10, 20, 30, 40, 50, 100]:
states = estimate_states(n)
magnitude = f"10^{int(math.log10(states))}"
print(f"{n:<12} {states:<20,} {magnitude}")Explosion combinatoire du nombre d'etats
==================================================
Predicats Etats possibles Ordre de grandeur
--------------------------------------------------
10 1,024 10^3
20 1,048,576 10^6
30 1,073,741,824 10^9
40 1,099,511,627,776 10^12
50 1,125,899,906,842,624 10^15
100 1,267,650,600,228,229,401,496,703,205,376 10^30La sortie démontre pourquoi les heuristiques sont essentielles en planification.
Analyse de la croissance :
| Prédicats | États possibles | Ordre de grandeur | Temps estimé* |
|---|---|---|---|
| 10 | 1,024 | 10³ | < 1 seconde |
| 20 | ~1 million | 10⁶ | quelques secondes |
| 30 | ~1 milliard | 10⁹ | plusieurs minutes |
| 40 | ~1 trillion | 10¹² | plusieurs heures |
| 50 | ~1 quadrillion | 10¹⁵ | plusieurs jours |
| 100 | ~1.3×10³⁰ | 10³⁰ | impossible |
*Hypothèse : 1 million d’états explorés par seconde
Points clés : 1. La croissance est exponentielle : chaque prédicat double le nombre d’états 2. L’exploration exhaustive devient rapidement impraticable 3. Les heuristiques guident la recherche vers les états prometteurs 4. Les planificateurs modernes utilisent des heuristiques comme \(h^{FF}\), \(h^{LM-cut}\)
Note technique : C’est le fameux “fléau de la dimensionnalité”. C’est pourquoi des techniques comme A* avec heuristique admissible, la recherche en avant (forward search), et la détection de redondances sont indispensables pour traiter des problèmes réels.
Une heuristique \(h(s)\) estime le cout pour atteindre le but depuis l’etat \(s\).
Proprietes importantes :
| Propriete | Definition | Consequence |
|---|---|---|
| Admissible | \(h(s) \leq h^*(s)\) (ne surestime jamais) | Optimalite avec A* |
| Coherente | \(h(s) \leq c(s,s') + h(s')\) | Convergence monotone |
| Informee | \(h(s)\) proche de \(h^*(s)\) | Recherche plus efficace |
Heuristiques classiques que nous explorerons dans les notebooks suivants : - \(h^{add}\) : Heuristique additive - \(h^{max}\) : Heuristique maximum - \(h^{FF}\) : Heuristique Fast Forward - \(h^{LM-cut}\) : Heuristique Landmark-Cut
Appliquons le pattern de modelisation (types -> fluents -> actions -> etat initial -> but) a un problème de livraison plus realiste. Un robot doit recuperer un colis au depot et le livrer a une destination, en se deplacant entre deux lieux.
Problème : - Lieux : depot, destination - Robot : commence au depot, mains vides - Colis : se trouve au depot - But : livrer le colis a la destination
Actions necessaires : - Se deplacer entre les lieux - Prendre le colis (si on est au même endroit) - Deposer le colis (si on le porte)
# Exemple guide 1 : Planification de livraison avec unified-planning
if UP_OK:
from unified_planning.environment import Environment
from unified_planning.engines import PlanGenerationResultStatus
from collections import OrderedDict
# Etape 1 : Creation de l'environnement et des types
env2 = Environment()
Location = env2.type_manager.UserType('Location')
Robot = env2.type_manager.UserType('Robot')
Package = env2.type_manager.UserType('Package')
# Etape 2 : Definition des fluents (predicats dynamiques)
robot_at_sig = OrderedDict([('r', Robot), ('l', Location)])
robot_at = Fluent('robot_at', BoolType(), _signature=robot_at_sig, environment=env2)
package_at_sig = OrderedDict([('p', Package), ('l', Location)])
package_at = Fluent('package_at', BoolType(), _signature=package_at_sig, environment=env2)
carrying_sig = OrderedDict([('r', Robot), ('p', Package)])
carrying = Fluent('carrying', BoolType(), _signature=carrying_sig, environment=env2)
# Etape 3 : Definition des actions
move_params = OrderedDict([('r', Robot), ('from_loc', Location), ('to_loc', Location)])
move = InstantaneousAction('move', _parameters=move_params, _env=env2)
r = move.r; from_loc = move.from_loc; to_loc = move.to_loc
move.add_precondition(robot_at(r, from_loc))
move.add_effect(robot_at(r, from_loc), False)
move.add_effect(robot_at(r, to_loc), True)
pick_params = OrderedDict([('r', Robot), ('p', Package), ('l', Location)])
pick = InstantaneousAction('pick', _parameters=pick_params, _env=env2)
r = pick.r; p = pick.p; l = pick.l
pick.add_precondition(robot_at(r, l))
pick.add_precondition(package_at(p, l))
pick.add_effect(carrying(r, p), True)
pick.add_effect(package_at(p, l), False)
drop_params = OrderedDict([('r', Robot), ('p', Package), ('l', Location)])
drop = InstantaneousAction('drop', _parameters=drop_params, _env=env2)
r = drop.r; p = drop.p; l = drop.l
drop.add_precondition(robot_at(r, l))
drop.add_precondition(carrying(r, p))
drop.add_effect(carrying(r, p), False)
drop.add_effect(package_at(p, l), True)
# Etape 4 : Instance du probleme
delivery_problem = Problem('delivery', env2)
depot_obj = Object('depot', Location, environment=env2)
dest_obj = Object('dest', Location, environment=env2)
rob_obj = Object('rob', Robot, environment=env2)
pkg_obj = Object('pkg', Package, environment=env2)
for obj in [depot_obj, dest_obj, rob_obj, pkg_obj]:
delivery_problem.add_object(obj)
delivery_problem.add_fluent(robot_at, default_initial_value=False)
delivery_problem.add_fluent(package_at, default_initial_value=False)
delivery_problem.add_fluent(carrying, default_initial_value=False)
delivery_problem.add_action(move)
delivery_problem.add_action(pick)
delivery_problem.add_action(drop)
delivery_problem.set_initial_value(robot_at(rob_obj, depot_obj), True)
delivery_problem.set_initial_value(package_at(pkg_obj, depot_obj), True)
delivery_problem.add_goal(package_at(pkg_obj, dest_obj))
print("Probleme 'delivery' cree avec succes")
print(f" Actions : {[a.name for a in delivery_problem.actions]}")
print(f" But : package_at(pkg, dest)")
# Etape 5 : Resolution
try:
with OneshotPlanner(name='pyperplan') as planner:
result = planner.solve(delivery_problem)
if result.status == PlanGenerationResultStatus.SOLVED_SATISFICING:
print(f"\nPlan optimal trouve ({len(result.plan.actions)} actions) :")
print("=" * 50)
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("=" * 50)
else:
print(f"Statut: {result.status}")
except Exception:
print(f"\nPlan attendu (3 actions) :")
print("=" * 50)
print(" 1. pick(rob, pkg, depot)")
print(" 2. move(rob, depot, dest)")
print(" 3. drop(rob, pkg, dest)")
print("=" * 50)
else:
print("unified-planning non disponible")Probleme 'delivery' cree avec succes
Actions : ['move', 'pick', 'drop']
But : package_at(pkg, dest)
Plan optimal trouve (3 actions) :
==================================================
1. pick(rob, pkg, depot)
2. move(rob, depot, dest)
3. drop(rob, pkg, dest)
==================================================Le planificateur produit un plan en 3 actions, qui est optimal pour ce problème :
| Étape | Action | Effet |
|---|---|---|
| 1 | pick(rob, pkg, depot) |
Le robot prend le colis au depot |
| 2 | move(rob, depot, dest) |
Le robot se deplace vers la destination |
| 3 | drop(rob, pkg, dest) |
Le robot depose le colis a destination |
Analyse du plan : - Le colis est ramasse avant le deplacement (precondition de move non liee au colis) - L’ordre pick -> move -> drop respecte toutes les preconditions
Points cles de la modelisation : 1. Separation type/objet : Les types Location, Robot, Package sont generiques ; les objets concrets (depot, rob, pkg) sont l’instance 2. Actions parametrees : move, pick, drop sont des schemas reutilisables pour tout couple d’objets 3. Fluent carrying : Encode la relation “le robot porte le colis” – necessaire pour eviter de prendre deux fois le même colis 4. default_initial_value=False : Tous les predicats sont faux par defaut, seuls les etats vrais sont declares explicitement
Note technique : Le modèle ne declare que les objets strictement necessaires au but (
depot,dest,rob,pkg). Un modèle plus riche pourrait inclure des lieux supplementaires (entrepot, garage…) que le planificateur ignorerait car non pertinents pour atteindre le but – le plan optimal resteraitpick -> move -> drop. Cette instance reste minimale par souci de lisibilite : le code instancie exactement les 4 objets (depot,dest,rob,pkg) que le butpackage_at(pkg, dest)mobilise.
Soit le problème suivant : - Etat initial : a(Paris), billet(Paris, Lyon) - But : a(Lyon) - Actions : - acheter_billet(X, Y) : precondition a(X), effet billet(X, Y) - prendre_train(X, Y) : precondition a(X), billet(X, Y), effet a(Y), not(a(X))
Questions : 1. Combien d’actions sont applicables dans l’etat initial ? 2. Quel est le plan optimal ? 3. Combien d’etats sont accessibles au maximum ?
Etendez le problème de l’interrupteur avec : 1. Deux interrupteurs s1 et s2 2. Un but : les deux interrupteurs doivent etre allumes 3. Etat initial : s1 allume, s2 eteint
Trouvez le plan optimal avec unified-planning.
# Exercice 2 : Deux interrupteurs
# Etendez le modele de l'interrupteur (probleme "light-switch" plus haut) a DEUX
# interrupteurs s1 et s2.
# - Etat initial : s1 allume, s2 eteint
# - But : les deux interrupteurs allumes
# Modelisez le probleme, resolvez-le avec un OneshotPlanner et affichez le plan optimal.
if UP_OK:
# A vous de jouer.
print("Exercice 2 a completer")Exercice 2 a completerGeneralisez le problème de l’interrupteur a N interrupteurs controlant une seule lampe.
Objectif : Ecrire une fonction qui genere un problème UP avec N interrupteurs, ou la lampe est allumee si au moins un interrupteur est sur ON.
Indices : - # Étape 1 : Créer N fluents booléens switch_i et un fluent light - # Étape 2 : Définir une action toggle_i pour chaque interrupteur - # Étape 3 : Le but est light = True - # Étape 4 : Verifier que le plan trouve a au plus N actions
if UP_OK:
from unified_planning.shortcuts import *
from unified_planning.engines import PlanGenerationResultStatus
def plan_multi_switch(n_switches=3):
"""Genere et resout un probleme de N interrupteurs."""
# TODO etudiant: creer le probleme avec n_switches interrupteurs
return [] # TODO etudiant: retourner la liste des actions du plan
plan = plan_multi_switch(3)
print(f"Plan pour 3 interrupteurs: {plan}")
print("Exercice a completer")Plan pour 3 interrupteurs: []
Exercice a completerIndice : un seul problème avec deux objets Switch, un but conjonctif (les deux interrupteurs allumes). Les actions turn_on / turn_off définies plus haut sont generiques et se reutilisent telles quelles.
Pour chaque scénario ci-dessous, identifiez quelle hypothese STRIPS est violee et expliquez pourquoi :
| Scénario | Hypothese violee | Pourquoi ? |
|---|---|---|
| Un robot qui se deplace et dont la batterie diminue progressivement | ? | ? |
| Un jeu ou les des determinent le résultat d’une action | ? | ? |
| Un environnement avec d’autres agents qui agissent simultanement | ? | ? |
| Une voiture autonome qui ne connait pas l’etat du traffic | ? | ? |
Completez le tableau. Les hypotheses STRIPS a considerer sont rappelees en section 2.1 : statique, déterministe, observable, discret, instantane.
| Concept | Definition |
|---|---|
| Planification | Trouver une sequence d’actions de I vers G |
| Etat | Ensemble de predicats vrais a un instant |
| Action | Transition avec preconditions et effets (add/del) |
| Plan | Sequence d’actions executable |
| Domaine | Schema general (types, predicats, actions) |
| Problème | Instance spécifique (objets, init, but) |
| Hypothese | Description |
|---|---|
| Statique | Environnement ne change que par les actions de l’agent |
| Déterministe | Effets uniques et predictibles |
| Observable | Etat courant parfaitement connu |
| Discret | Etats et actions denombrables |
| Instantane | Actions sans duree |
Dans les notebooks suivants, nous approfondirons :
Notebook suivant : Planners-2-PDDL-Basics