Συστήματα ευριστικού σχεδιασμού ενεργειών

Abstract

In this dissertation a new heuristic planning system, which searches for plans in the space of the states and constructs its heuristic function in a domain-independent way, is presented. The system is called GRT and it adopts the STRIPS formalism for the domain and problem representation. The system operation for solving planning problems consists of two main phases: The pre-processing phase and the search phase. In the first phase it estimates the distances between each fact and the goals of the problem, in a backward direction. In the second phase, these estimates are used in order to further estimate the distance between each intermediate state and the goals, guiding so the search process in a forward direction and on a best-first basis. The benefit from the adoption of opposite directions for the heuristic construction and the state-space traversal is that the time consuming heuristic construction process has to be repeated once only and thus the overall planning process is significantly accelerated. The dissertation presents two techniques that cope with the problems of the incomplete goal states and the implicit presence of facts in the initial state and the preconditions of the actions. For the first problem it is proposed the automatic incomplete state detection and enhancement technique, while for the second problem it is proposed the domain enrichment technique. Moreover, two solution preserving methods for increasing the efficiency of state-space planners are presented: the automatic detection and elimination of irrelevant objects and the numerical representation of resources. These methods succeed in reducing the size of the problems, i.e. the numbers of ground facts and actions. The dissertation presents extensive comparative performance results from several planning domains and with the most known and efficient planning systems of the recent years. The results show that GRT is among the more efficient planning systems, in terms of both planning time and plan length. Moreover, in many cases GRT clearly outperforms the other planning systems. Two extensions of the basic planning system GRT are presented in the dissertation: GRTSC and MO-GRT. The GRTSC system aims in overcoming the local optimal values that characterize every heuristic function, especially those that are constructed in a domain independent way, as the one of GRT. GRTSC takes as additional input domain specific knowledge, in the form of domain axioms, which is used to decompose the difficult problems in sequences of easier sub-problems that have to be solved in sequence. Experimental results have shown that GRTSC achieves a significant improvement in its efficiency, with respect to GRT, in domains where local optimal states arise. The MO-GRT system extends the capabilities of GRT in problems where many criteria, often contradictory, are of interest in the construction and evaluation of the resulting plans. Such criteria include the length of the plans, their duration, the cost and the profit of their execution and of course the time needed for their construction. These criteria arise in most of the real world problems. The MO-GRT system uses a weighted A* strategy and a multiobjective heuristic function, which is computed over a weighted hierarchy of user-defined criteria. Its computation is based on sets of non-dominated value-vectors assigned to the problem facts, which estimate the total cost of achieving the facts from the goals, using alternative paths. Experiments have shown that the criteria, their weights and their scales, affect significantly both the quality of the resulting plans and the planning time.