Hierarchical planning involving deadlines, travel time, and resources

This paper describes a planning architecture that supports a form of hierarchical planning well suited to applications involving deadlines, travel time, and resource considerations. The architecture is based upon a temporal database, a heuristic evaluator, and a decision procedure for refining partial plans. A partial plan consists of a set of tasks and constraints on their order, duration, and potential resource requirements. The temporal database records the partial plan that the planner is currently working on and computes certain consequences of that information to be used in proposing methods to further refine the plan. The heuristic evaluator examines the space of linearized extensions of a given partial plan in order to reject plans that fail to satisfy basic requirements (e.g., hard deadlines and resource limitations) and to estimate the utility of plans that meet these requirements. The information provided by the temporal database and the heuristic evaluator is combined using a decision procedure that determines how best to refine the current partial plan. Neither the temporal database nor the heuristic evaluator is complete and, without reasonably accurate information concerning the possible resource requirements of the tasks in a partial plan, there is a significant risk of missing solutions. A specification language that serves to encode expectations concerning the duration and resource requirements of tasks greatly reduces this risk, enabling useful evaluations of partial plans. Details of the specification language and examples illustrating how such expectations are exploited in decision making are provided. Cet article decrit une architecture de planification qui soutient une forme de planification hierarchique adaptee aux applications mettant en cause des limites, des temps de deplacement et des considerations au niveau des ressources. Cette architecture est fonction d'une base de donnees temporelle, d'un evaluateur heuristique et d'un processus decisionnel permettant de perfectionner des plans partiels. Un plan partiel consiste en une serie de taches ainsi que leurs contraintes au niveau de l'ordre, de la duree et des exigences possibles en matiere de ressources. La base de donnees temporelle enregistre le plan partiel sur lequel le planificateur travaille et evalue certaines consequences de ces donnees qui serviront a proposer des methodes de perfectionnement du plan. L'evaluation heuristique examine l'espace des extensions linearisees d'un plan partiel donne afin de rejeter les plans qui ne satisfont pas aux exigences de base (par ex.: dates limites serrees et limitations des ressources) et d'evaluer l'utilite des plans qui respectent ces exigences. Les renseignements fournis par la base de donnees temporelle et l'evaluation heuristique sont combines a l'aide d'un processus decisionnel qui determine la meilleure facon de perfectionner le plan partiel actuel. Ni la base de donnees temporelle, ni l'evaluateur heuristique ne sont complets. Sans des renseignements relativement precis concernant les exigences possibles au niveau des ressources des taches d'un plan partiel, il y a un important risque que des solutions nous echappent. Un language de specification qui sert a encoder les attentes concernant les exigences au niveau de la duree et des ressources des taches reduit grandement ce risque et permet des evaluations utiles de plans partiels. Des details au sujet du langage de specification et des exemples illustrant comment de telles attentes sont exploitees dans les processus decisionnel sont fournis.