Éric Beaudry

  Sommaire

 Liens

 

Eric Beaudry

Éric Beaudry
Gradué de l'Université de Sherbrooke
Département d'informatique

Laboratoires Planiart et Laborius

icône courriel Eric.Beaudry@USherbrooke.ca

Maintenant postdoctorant au NASA Ames Research Center, Californie, É-U

 






Entête

Doctorat : planification d'actions concurrentes avec incertitude


Résumé : Cette thèse présente des contributions dans le domaine de la planification en intelligence artificielle, et ce, plus particulièrement pour une classe de problèmes qui combinent des actions concurrentes (simultanées) et de l'incertitude. Deux formes d’incertitude sont prises en charge, soit sur la durée des actions et sur leurs effets.  Cette classe de problèmes est motivée par plusieurs applications réelles dont la robotique mobile, les jeux et les systèmes d’aide à la décision. Cette classe a notamment été identifiée par la NASA pour la planification des activités des rovers déployés sur Mars. Les algorithmes de planification présentés dans cette thèse exploitent une nouvelle représentation compacte d’états afin de réduire significativement l’espace de recherche. Des variables aléatoires continues sont utilisées pour modéliser l’incertitude sur le temps. Un réseau bayésien, qui est généré dynamiquement, modélise les dépendances entre les variables aléatoires et estime la qualité et la probabilité de succès des plans. Un premier planificateur, basé sur un algorithme de recherche à chaînage avant, prend en charge des actions ayant des durées probabilistes. Ce dernier génère des plans non conditionnels qui satisfont à une contrainte sur la probabilité de succès souhaitée. Un deuxième planificateur fusionne des plans non conditionnels afin de construire des plans conditionnels plus efficaces. Un troisième planificateur, nommé QuanPlan, prend également en charge l’incertitude sur les effets des actions. Afin de modéliser l’exécution simultanée d’actions aux effets indéterminés, QuanPlan s’inspire de la mécanique quantique où des états quantiques sont des superpositions d’états classiques. Un processus décisionnel de Markov (MDP) est utilisé pour générer des plans dans un espace d’états quantiques. L’optimalité, la complétude, ainsi que les limites de ces planificateurs sont discutées. Des comparaisons avec d’autres planificateurs ciblant des classes de problèmes similaires démontrent l’efficacité des méthodes présentées. Enfin, une contribution complémentaire domaine la planification de trajectoires est présentée.

Télécharger : Thèse | Présentation.


[ Article ]
[ Article ]
Abstract. Planning with actions concurrency under resources and time uncertainty has been recognized as a challenging and interesting problem. Most current approaches rely on a discrete model to represent resources and time, which contributes to the combinatorial explosion of the search space when dealing with both actions concurrency and resources and time uncertainty. A recent alternative approach uses continuous random variables to represent the uncertainty on time, thus avoiding the state-space explosion caused by the discretization of timestamps. We generalize this approach to consider uncertainty on both resources and time. Our planner is based on a forward chaining search in a state-space where the state representation is characterized by a set of object and numeric state variables. Object state variables are associated with random variables tracking the time at which the state variables’ current value has been assigned. The search algorithm dynamically generates a Bayesian network that models the dependency between time and numeric random variables. The planning algorithm queries the Bayesian network to estimate the probability that the resources (numerical state variables) remain in a valid state, the probability of success and the expected cost of the generated plans. Experiments were performed on a transport domain in which we introduced uncertainty on the duration of actions and on the fuel consumption of trucks.

[ Article ] [ Présentation ]
Abstract. An interesting class of planning domains, including planning for daily activities of Mars rovers, involves achievement of goals with time constraints and concurrent actions with probabilistic durations. Current probabilistic approaches, which rely on a discrete time model, introduce a blow up in the search state-space when the two factors of action concurrency and action duration uncertainty are combined. Simulation-based and sampling probabilistic planning approaches would cope with this state explosion by avoiding storing all the explored states in memory, but they remain approximate solution approaches. In this paper, we present an alternative approach relying on a continuous time model which avoids the state explosion caused by time stamping in the presence of action concurrency and action duration uncertainty. Time is represented as a continuous random variable. The dependency between state time variables is conveyed by a Bayesian network, which is dynamically generated by a state-based forward-chaining search based on the action descriptions. A generated plan is characterized by a probability of satisfying a goal, and the evaluation of this probability is based on the Bayesian network.

[ Article ] [ Présentation ]
Résumé. La génération de plans d'action concurrente avec incertitude au niveau des ressources et du temps représente une classe de problèmes complexes dans le domaine de la planification en intelligence artificielle. Plusieurs applications pourraient bénéficier de meilleurs planificateurs pour cette classe de problèmes. L'une d'entre elles est le contrôle de robots mobiles et autonomes envoyés sur la planète Mars. Les futures générations de robots martiens devront être en mesure de planifier leurs actions tout en considérant l'incertitude sur le temps (durée des actions) et les ressources (ex.: quantité d'énergie consommée). Les approches actuelles s'avèrent généralement limitées pour des problèmes de petite taille et sont souvent très gourmandes en mémoire. Une nouvelle approche pour ce type de planification sera présentée.

[Présentation]
Abstract. Behavior-based architectures use behaviors as building blocks for decision-making and action execution processes.  Behaviors are distributed and evaluated in parallel for the control of the robot, taking real-time inputs from sensory data and sending real-time commands to effectors.  No centralized components exist in these architectures, each module carrying out its own strategy independently, making an overall behavior emerge from the interaction between the concurrently executed modules and the environment.  In this paper, we discuss the use of a reactive Hierarchical Task Network (HTN) planner in a behavior-based robot architecture.  The planner in this architecture is not a central component on which everything else relies on, but acts as one of the motivational modules recommending tasks to be executed and influencing the selection and configuration of behaviors.  The planning module allows the behavior-based architecture to deal with tasks with priorities, flexible time constraints and on-line planning using a simple but very effective reactive planning strategy.  We demonstrate our approach in the context of making a robot attend a conference.

[ Article ]  [ Présentation ]
Résumé. Pour plusieurs applications comme les robots explorateurs sur Mars et l'observation de la Terre, des plans doivent être générés afin d'automatiser une partie des activités. Les planificateurs utilisés doivent être capables de coordonner plusieurs actions concurrentes afin réduire la durée totale des activités. Puisque ces systèmes évoluent dans des environnements incertains, ces systèmes doivent faire face à différents imprévus. Une partie importante de cette incertitude est liée aux ressources et temps. Il existe plusieurs stratégies pour pallier les différents imprévus, comme la replanification. Cependant, ces stratégies peuvent entraîner une exécution inefficace et mener à des échecs ou des abandons de tâches. Afin de rendre les robots et agents autonomes plus efficaces et fiables, il peut être préférable de considérer cette incertitude au moment de la planification. Jusqu'à présent, très peu de travaux ont été réalisés au niveau de la planification concurrente avec incertitude. Dans cette proposition de sujet de doctorat, des idées d'amélioration d'algorithmes de planification sont présentées. Il est entre autres proposé d'améliorer un planificateur HTN existant en lui intégrant un modèle d'incertitude au niveau du temps et des ressources. Cela lui permettra de générer des plans conditionnels permettant de faire face à divers imprévus. L'algorithme sera aussi adapté pour être plus dynamique pour d'éventuelles replanifications et sera capable de générer des plans à satisfaction partielle. Une autre idée consiste à l'élaboration d'une nouvelle heuristique mieux adaptée à l'incertitude. Ces améliorations seront validées sur des scénarios inspirés des robots sur Mars. Une autre partie des travaux porte sur la prise en charge de l'incertitude de la localisaiton au moment de la planification.

[ Document ]  [ Présentation]

Enseignement et supervision de projets



Maîtrise : planification en intelligence artificielle pour la robotique mobile


Réalisations informatique


Champs d'intérêt




Liens

Université de Sherbrooke


Prévisions météo et conditions des routes

Granby | Sherbrooke | Montréal | St-Hyacinthe | Québec | Victoria
Autoroute 10 | Région Estrie


Nouvelles


Autres

 



© Éric Beaudry, 2006-2011. Tous droits réservés. ¦ webdesign par Émilie Viau

HTML 4.01 Transitional valide!Valid CSS!