Elodie Chanthery Sylvain Damiani - Laboratoire … · Suivi de Situation capteurs ... ∨ par des fonctions de pénalisation dans le critère ... Wolfe, application d’un simplexe

Séminaire FERIA

Systèmes Décisionnels

18 janvier 2005

Elodie Chanthery

Sylvain Damiani

Décision en ligne pourengins autonomes

Page 2 FERIA - Systèmes Décisionnels

PlanPlan

≡ Contexte

∨ Environnement opérationnel

∨ de l’autonomie opérationnelle à l’autonomie décisionnelle

∨ domaines applicatifs

∨ objectifs et contraintes

≡ But : prendre la meilleure décision

≡ Les méthodes d’optimisation

≡ Deux exemples

∨ drone

∨ satellite


Contexte de la présentationContexte de la présentation

Processus de

Suivi de

Situation

capteursProcessus

de Décision /

Planification

environnement

opérateur

actionneurs

Mission

Communication

autonomie

charges utiles

engin

Décisiondistribuée


De l’autonomie opérationnelle ...De l’autonomie opérationnelle ...

≡ Niveau d’autonomie ↔ interaction entre l’engin et lesopérateurs

∨ autonomie avec abstraction des décisions opérateur

≡ Niveau 0 : engin téléopéré : autonomie opérationnelle,l’engin réalise des fonctions de commande de bas

niveau

≡ Exemple

Concept Victor 6000 © Ifremer - Alris Communication


… Aux besoins en autonomie décisionnelle… Aux besoins en autonomie décisionnelle

≡ Communications fortement limitées entre l’engin et les

opérateurs

≡ Environnement mal connu, incertain, dynamique,

changeant, hostile, dangereux

≡ Evénements dont l’occurrence est imprévisible

∨ ex : nouveau danger, nouveaux objectifs

→ Besoins en autonomie décisionnelle


Contexte: domaines applicatifsContexte: domaines applicatifs

≡ Robotique terrestre

≡ Robotique sous-marine

≡ Avions sans pilote (drones)

≡ Hélicoptères

≡ Satellites

≡ Applications civiles et militaires


Objectifs et contraintesObjectifs et contraintes

Objectifs

≡ Développer la décision autonome en ligne

≡ Réagir aux imprévus

≡ Optimiser la décision en fonction de l’état et de

l’environnement

Contraintes sur la prise de décision

≡ Limitation en CPU, en mémoire vive

≡ Interruptions possibles

≡ Temps de réponse en accord avec les exigences du

problème

Solution Développer des algorithmes anytime si

possible, ou gloutons


PlanPlan

≡ Contexte







≡ Deux exemples

∨ drone

∨ satellite


Objectifs de la planificationObjectifs de la planification

≡ Sélectionner un sous-ensemble d’objectifs

≡ Eventuellement les ordonner

≡ Sortie : un plan ou une décision

≡ Instants de décision

≡ Décision et raisonnement

act_2 t

act_1 tHorizon de décision

Horizon de raisonnement

act_1 tTemps pour raisonner


Contraintes sur la décision :prise en compte des ressourcesContraintes sur la décision :prise en compte des ressources

≡ Contraintes dures

∨ contraintes physiques

∨ cadre du modèle

ex: quantité de carburant embarqué, degré de déchargemaximal d’une batterie, contraintes dynamiques sur l’engin(vitesses min, max)

≡ Contraintes molles

→ si non respectées, dégradation de la qualité de la solution

ex: finir la mission avec plus ou moins de carburant

≡ Prise en compte des contraintes sur les ressources

∨ par des inégalités Ce(re) ≥ 0

∨ par des fonctions de pénalisation dans le critère

∨ vérification de l’applicabilité du plan après optimisation


Critères de qualité de la solutionCritères de qualité de la solution

≡ Utilité globale maximale, fonction du niveau d’énergie,

du niveau de mémoire, des observations

≡ Différence entre des coûts et des gains

≡ Autres critères possibles: longueur, coût, durée ...

≡ Particularité de certains problèmes réels

∨ pas d’inégalité triangulaire pour les coûts, coûts non additifs

∨ ressources non décomposables

)m,e,j(Umax *

m,e,ij≤

min J = Re(re) -�∈Eoo

ooooo )'r,'t,r,(tR

récompenses coûts


PlanPlan

≡ Contexte







≡ Deux exemples

∨ drone

∨ satellite


Les algorithmes anytimeLes algorithmes anytime

≡ Caractéristiques

∨ Solution valide à chaque instant

∨ Qualité du résultat croissante à durée de raisonnementcroissante

� utilisation au mieux du temps disponible

≡ Utilisation

∨ 1 activité : toujours actif, relancé à chaque événement

∨ Plusieurs activités : optimisation du temps laissé pour ladécision concernant chaque activité (deliberation scheduling)

Utilité

Temps de calcul


La programmation dynamiqueLa programmation dynamique

≡ Caractéristiques

∨ Résolution d'un problème de manière itérative

∨ Réutilisation directe de résultats de sous-problèmes

≡ Avantages

∨ Si chaque sous-problème est une solution valide

et si la qualité du résultat ↑ quand le niveau du sous-problème ↑

� algorithme anytime

∨ Optimalité, complexité en temps réduite

≡ Inconvénients

∨ Complexité en espace non négligeable

∨ Fragilité

≡ Autres méthodes (non optimales)

∨ Gloutons + recherche locale

∨ Gloutons stochastiques


Recherche arborescenteRecherche arborescente

≡ Caractéristiques∨ Recherche d’un plan pas à pas

∨ Optimisation de sous-problèmes durant la recherche

≡ Justifications

∨ Problème où la propriété de l’inégalité triangulaire ne s’applique pas

∨ Ressources non décomposables sur les arcs

→ Algorithmes utilisant le déroutement (Ford, Dijkstra) impossible

≡ Avantages

∨ Prise en comptes de contraintes temporelles sur les nœuds

∨ Gestion de ressources non décomposables

≡ Inconvénient

∨ Complexité → nécessité d’une bonne méthode d’élagage


Recherche arborescenteFormalisme utiliséRecherche arborescenteFormalisme utilisé

≡ N ensemble des nœuds (étapes du plan)

≡ W = {W1, …, Wp} une partition de N

≡ relation S : S(Wi) est l’ensemble des successeurs de Wi

≡ But : trouver une séquence d’états W1, …, Wq telle que

∨ W1 = Ws

∨ Wq = We

∨ ∀ i, Wi+1 ∈S(Wi) en minimisant le critère et en respectant lescontraintes


Recherche arborescenteFormalisme utilisé (suite)Recherche arborescenteFormalisme utilisé (suite)

≡ Niveau I réalisation des objectifs

∨ Définition d’un objectif

≡ Niveau II : chemin et ordonnancement

∨ il existe un ou plusieurs arcs entre n1∈N et n2∈N ssi il existe i et j

tels que: n1∈Wi, n2 ∈Wj et Wj ∈S(Wi)

∨ Spécialisation des nœuds, modes d’accès

∨ Mi,j sous-ensemble des modes d’accès autorisés entre ni et nj

∨ Fenêtres temporelles sur les nœuds : tjmin ≤ tj ≤ tjmax

∨ Ressources décomposables, non décomposables et contraintes


Recherche arborescente de type A*algorithme utiliséRecherche arborescente de type A*algorithme utilisé

DébutInitialisation

Placer IW dans Liste Ptant que Liste P n’est pas vide faire

pour tout v dans S(û) faire

Construire l’itinéraire de IW jusqu’à vOptimiser J en choisissant les dates pour chaque nœud en respectant les contraintesCalculer J = gX de IW à v

si v ∈We et gX < BORNE alors BORNE = gXElaguer l’arbre d’exploration

finMettre les éléments de S(û) dans Liste PEffacer û de P

finfin

Chercher une première solution admissible de coût C0; BORNE = Co

≡ Méthode de recherche d’une première solution admissible

≡ 4 méthodes d’évaluation du coût d’un nœud courant à un nœud fin

≡ 2 méthodes d’élagage

≡ 4 méthodes de rangement

≡ gestion des modes d’accès

^

pour tous les modes d’accès appliqués à v faire

fin

Calculer l’évaluation du critère de v jusqu’à un nœud fin

Mettre les éléments de S(û) dans Liste P

Elaguer l’arbre d’exploration

Prise en compte descontraintes temporelles

Optimisation d’un critère non linéairesous contraintes linéaires• utilisation de l’algorithme de Frank &Wolfe, application d’un simplexe• prise en compte des contraintes nonlinéaires par des termes de pénalisation


PlanPlan

≡ Contexte







≡ Deux exemples

∨ drone

∨ satellite


Planification de mission pour un Véhicule AérienAutonomePlanification de mission pour un Véhicule AérienAutonome

≡ Mission militaire d’observation

≡ Choix d’un engin de type MALE

≡ Environnement 3D dynamique,

incertain et dangereux

≡ Planification a priori

Objectifs

- Sélectionner et ordonner le meilleur

sous-ensemble d’objectifs à réaliser

- Déterminer les vitesses le long de

l’itinéraire

- Maximiser les gains, minimiser les coûts,

respecter les contraintes


≡ Première solution : < 5s

≡ Modes d’accès (= de navigation) : critère mais temps de calcul

✕ 50 et ✕ 14 dans les plus mauvais cas

≡ Méthodes de rangement: temps de calcul ÷ 4

Les tests : mode « nominal »Les tests : mode « nominal »

≡ Utilisation de la recherche arborescente


Les tests : replanification en ligneLes tests : replanification en ligne

≡ Modes d’accès (= de navigation)

critère avec 2 modes de navigation possible << critère avec mode unique

≡ Fin des calculs en moins de 0,5 s, première (et meilleure) solution

donnée en 0,06 s


Gestion autonome d'un satellite de surveillanceGestion autonome d'un satellite de surveillance

≡ 2 activités :

∨ Observation

∨ Télédéchargement


Gestion de l'observation à bordGestion de l'observation à bord

≡ Caractéristiques d'une observation :

∨ Dates de début et de fin connues et fixées

∨ Angle de dépointage constant

∨ Consommation de ressources connue

∨ Utilité associée à la réalisation

u(1)

u(2)

u(3)

u(4)

HDHR

t

Date courante

?



≡ Utilisation de la programmation dynamique

∨ Sens direct

∨ Prise en compte des ressources

U i u i max j C i U j

V i max j i U j max V i 1 ,U i

U i , m ,e u i max j C i ,m ' ,e ' U j , m ' , e '

Mémoire utilisée

Observations

0 1 2 3

Niveau maximal



• Utilisation de la programmation dynamique

• Sens direct

• Prise en compte des ressources

• Discrétisation

U i u i max j C i U j

U i , m ,e u i max j C i ,m ' ,e ' U j , m ' , e '

Mémoire utilisée

Observations

0 1 2 3

Niveau maximal

Niveau intermédiaire

V i max j i U j max V i 1 ,U i


ConclusionsConclusions

≡ Prise de décision en ligne pour engins autonomes

∨ Importance de la prise en compte des ressources

∨ Critères variés

∨ Spécificité des problèmes réels : ressources nondécomposables

∨ Algorithmes anytime

≡ Méthodes adaptées à un problème donné

∨ Programmation dynamique

∨ Recherche arborescente

≡ Développement d’un ou plusieurs modules de

planification à intégrer avec un superviseur

≡ La réalisation du plan sera non optimale (en global) en

cas d’aléas

Documents

Elodie Chanthery Sylvain Damiani - Laboratoire … · Suivi de Situation capteurs ... ∨ par des fonctions de pénalisation dans le critère ... Wolfe, application d’un simplexe