Planification et ordonnancement automatisées - Automated planning and scheduling

La planification et la planification automatisées , parfois désignées simplement comme la planification de l'IA , est une branche de l' intelligence artificielle qui concerne la réalisation de stratégies ou de séquences d'action, généralement destinées à être exécutées par des agents intelligents , des robots autonomes et des véhicules sans pilote . Contrairement aux problèmes classiques de contrôle et de classification , les solutions sont complexes et doivent être découvertes et optimisées dans un espace multidimensionnel. La planification est également liée à la théorie de la décision .

Dans les environnements connus avec des modèles disponibles, la planification peut être effectuée hors ligne. Des solutions peuvent être trouvées et évaluées avant l'exécution. Dans des environnements dynamiquement inconnus, la stratégie doit souvent être révisée en ligne. Les modèles et les politiques doivent être adaptés. Les solutions recourent généralement à des processus itératifs d' essais et d'erreurs couramment observés en intelligence artificielle . Il s'agit notamment de la programmation dynamique , de l' apprentissage par renforcement et de l' optimisation combinatoire . Les langages utilisés pour décrire la planification et l'ordonnancement sont souvent appelés langages d'action .

Aperçu

Étant donné une description des états initiaux possibles du monde, une description des objectifs souhaités et une description d'un ensemble d'actions possibles, le problème de planification est de synthétiser un plan qui est garanti (lorsqu'il est appliqué à l'un des états initiaux) pour générer un état qui contient les objectifs souhaités (un tel état est appelé état objectif).

La difficulté de la planification dépend des hypothèses simplificatrices employées. Plusieurs classes de problèmes de planification peuvent être identifiées en fonction des propriétés des problèmes dans plusieurs dimensions.

Les actions sont-elles déterministes ou non déterministes ? Pour les actions non déterministes, les probabilités associées sont-elles disponibles?
Les variables d'état sont-elles discrètes ou continues ? S'ils sont discrets, n'ont-ils qu'un nombre fini de valeurs possibles ?
L'état actuel peut-il être observé sans ambiguïté ? Il peut y avoir une observabilité totale et une observabilité partielle.
Combien y a-t-il d'états initiaux, finis ou arbitrairement nombreux ?
Les actions ont-elles une durée ?
Plusieurs actions peuvent-elles être entreprises simultanément ou une seule action est-elle possible à la fois?
L'objectif d'un plan est-il d'atteindre un état d'objectif désigné ou de maximiser une fonction de récompense ?
Y a-t-il un seul agent ou y a-t-il plusieurs agents? Les agents sont-ils coopératifs ou égoïstes? Tous les agents construisent-ils leurs propres plans séparément, ou les plans sont-ils construits de manière centralisée pour tous les agents ?

Le problème de planification le plus simple possible, connu sous le nom de problème de planification classique, est déterminé par:

un état initial unique connu,
actions sans durée,
actions déterministes,
qui ne peut être pris qu’un à la fois,
et un seul agent.

Puisque l'état initial est connu sans ambiguïté et que toutes les actions sont déterministes, l'état du monde après toute séquence d'actions peut être prédit avec précision, et la question de l'observabilité n'est pas pertinente pour la planification classique.

De plus, les plans peuvent être définis comme des séquences d'actions, car on sait toujours à l'avance quelles actions seront nécessaires.

Avec des actions non déterministes ou d'autres événements hors du contrôle de l'agent, les exécutions possibles forment un arbre, et les plans doivent déterminer les actions appropriées pour chaque nœud de l'arbre.

Les processus décisionnels de Markov en temps discret (MDP) posent des problèmes de planification avec :

actions sans durée,
actions non déterministes avec probabilités,
observabilité totale,
maximisation d'une fonction de récompense,
et un seul agent.

Lorsque l'observabilité totale est remplacée par l'observabilité partielle, la planification correspond à un processus de décision de Markov partiellement observable (POMDP).

S'il y a plus d'un agent, nous avons une planification multi-agents , qui est étroitement liée à la théorie des jeux .

Planification indépendante du domaine

Dans la planification de l'IA, les planificateurs saisissent généralement un modèle de domaine (une description d'un ensemble d'actions possibles qui modélisent le domaine) ainsi que le problème spécifique à résoudre spécifié par l'état initial et l'objectif, contrairement à ceux dans lesquels il n'y a pas domaine d'entrée spécifié. Ces planificateurs sont appelés «indépendants du domaine» pour souligner le fait qu'ils peuvent résoudre des problèmes de planification dans un large éventail de domaines. Des exemples typiques de domaines sont l'empilement de blocs, la logistique, la gestion du flux de travail et la planification des tâches du robot. Par conséquent, un seul planificateur indépendant du domaine peut être utilisé pour résoudre les problèmes de planification dans tous ces différents domaines. D'autre part, un planificateur d'itinéraire est typique d'un planificateur spécifique à un domaine.

Planification des langages de modélisation de domaine

Les langages les plus couramment utilisés pour représenter les domaines de planification et les problèmes de planification spécifiques, tels que STRIPS et PDDL pour la planification classique, sont basés sur des variables d'état. Chaque état possible du monde est une affectation de valeurs aux variables d'état, et les actions déterminent comment les valeurs des variables d'état changent lorsque cette action est effectuée. Puisqu'un ensemble de variables d'état induit un espace d'états dont la taille est exponentielle dans l'ensemble, la planification, comme de nombreux autres problèmes de calcul, souffre de la malédiction de la dimensionnalité et de l' explosion combinatoire .

Un autre langage pour décrire les problèmes de planification est celui des réseaux de tâches hiérarchiques , dans lesquels un ensemble de tâches est donné, et chaque tâche peut être soit réalisée par une action primitive, soit décomposée en un ensemble d'autres tâches. Cela n'implique pas nécessairement des variables d'état, bien que dans des applications plus réalistes, les variables d'état simplifient la description des réseaux de tâches.

Algorithmes de planification

Planification classique

recherche d'espace d'états de chaînage avant , éventuellement améliorée avec l' heuristique
recherche de chaînage vers l'arrière , éventuellement améliorée par l'utilisation de contraintes d'état (voir STRIPS , graphplan )
planification des commandes partielles

Réduction à d'autres problèmes

réduction au problème de satisfiabilité propositionnelle ( satplan ).
réduction à la vérification de modèle - les deux sont essentiellement des problèmes de traversée des espaces d'états, et le problème de planification classique correspond à une sous-classe de problèmes de vérification de modèle.

Planification temporelle

La planification temporelle peut être résolue avec des méthodes similaires à la planification classique. La principale différence est, en raison de la possibilité de plusieurs actions se chevauchant temporellement avec une durée d'être prises simultanément, que la définition d'un état doit inclure des informations sur le temps absolu actuel et jusqu'où l'exécution de chaque action active s'est déroulée. En outre, dans la planification en temps rationnel ou réel, l'espace d'états peut être infini, contrairement à la planification classique ou à la planification avec un temps entier. La planification temporelle est étroitement liée aux problèmes de planification . La planification temporelle peut également être comprise en termes d' automates temporisés .

Planification probabiliste

La planification probabiliste peut être résolue avec des méthodes itératives telles que l' itération de valeur et l'itération de politique , lorsque l'espace d'état est suffisamment petit. Avec l'observabilité partielle, la planification probabiliste est résolue de manière similaire avec des méthodes itératives, mais en utilisant une représentation des fonctions de valeur définies pour l'espace des croyances au lieu des états.

Planification basée sur les préférences

Dans la planification basée sur les préférences, l'objectif n'est pas seulement de produire un plan, mais aussi de satisfaire les préférences spécifiées par l'utilisateur . A la différence de la planification basée sur les récompenses plus courante, correspondant par exemple aux MDP, les préférences n'ont pas nécessairement une valeur numérique précise.

Planification conditionnelle

La planification déterministe a été introduite avec le système de planification STRIPS , qui est un planificateur hiérarchique. Les noms des actions sont classés dans une séquence et il s'agit d'un plan pour le robot. La planification hiérarchique peut être comparée à un arbre de comportement généré automatiquement . L'inconvénient est qu'un arbre de comportement normal n'est pas aussi expressif qu'un programme informatique. Cela signifie que la notation d'un graphe de comportement contient des commandes d'action, mais pas de boucles ni d'instructions if-then. La planification conditionnelle surmonte le goulot d'étranglement et introduit une notation élaborée qui est similaire à un flux de contrôle , connu d'autres langages de programmation comme Pascal . C'est très similaire à la synthèse de programme , ce qui signifie qu'un planificateur génère un code source qui peut être exécuté par un interpréteur.

Un premier exemple de planificateur conditionnel est le « Warplan-C » qui a été introduit au milieu des années 1970. Quelle est la différence entre une séquence normale et un plan compliqué, qui contient des instructions if-then? Cela a à voir avec l'incertitude au moment de l' exécution d'un plan. L'idée est qu'un plan peut réagir à des signaux de capteurs qui sont inconnus du planificateur. Le planificateur génère deux choix à l'avance. Par exemple, si un objet a été détecté, l'action A est exécutée, si un objet est manquant, l'action B est exécutée. Un avantage majeur de la planification conditionnelle est la capacité de gérer des plans partiels . Un agent n'est pas obligé de tout planifier du début à la fin, mais peut diviser le problème en morceaux . Cela aide à réduire l'espace d'états et résout des problèmes beaucoup plus complexes.

Planification d'urgence

On parle de "contingent planning" lorsque l'environnement est observable grâce à des capteurs, qui peuvent être défaillants. Il s'agit donc d'une situation où l'agent planificateur agit sous des informations incomplètes. Pour un problème de planification contingente, un plan n'est plus une séquence d'actions mais un arbre de décision car chaque étape du plan est représentée par un ensemble d'états plutôt que par un seul état parfaitement observable, comme dans le cas de la planification classique. Les actions sélectionnées dépendent de l'état du système. Par exemple, s'il pleut, l'agent choisit de prendre le parapluie, et si ce n'est pas le cas, il peut choisir de ne pas le prendre.

Michael L. Littman a montré en 1998 qu'avec les actions de branchement, le problème de planification devient EXPTIME -complet. Un cas particulier de planification contiguë est représenté par les problèmes FOND - pour «pleinement observable et non déterministe». Si l'objectif est spécifié dans LTLf (logique temporelle linéaire sur trace finie), le problème est toujours EXPTIME-complet et 2EXPTIME-complet si l'objectif est spécifié avec LDLf.

Planification conforme

La planification conforme se produit lorsque l'agent est incertain de l'état du système et qu'il ne peut faire aucune observation. L'agent a alors des croyances sur le monde réel, mais ne peut pas les vérifier avec des actions de détection, par exemple. Ces problèmes sont résolus par des techniques similaires à celles de la planification classique, mais où l'espace d'état est exponentiel dans la taille du problème, en raison de l'incertitude sur l'état actuel. Une solution à un problème de planification conforme est une séquence d'actions. Haslum et Jonsson ont démontré que le problème de la planification conforme est EXPSPACE -complet, et 2EXPTIME-complet lorsque la situation initiale est incertaine, et qu'il n'y a pas de déterminisme dans les résultats des actions.

Déploiement de systèmes de planification

Le télescope spatial Hubble utilise un système à court terme appelé SPSS et un système de planification à long terme appelé Spike .

Voir également

Listes

Les références

Lectures complémentaires

Vlahavas, I. "Planification et ordonnancement" . EETN . Archivé de l'original le 22/12/2013.

Liens externes

Conférence internationale sur la planification et la planification automatisées

Languages

In other projects