Improving cost and probability estimates using interaction

Abstract

Automated Planning is concerned with finding a program of actions that given an initial state reaches a desired goal. This program can be a simple sequence or a more complex partially ordered collection of actions. When action outcomes are deterministic and information is perfect, it is called deterministic planning. Significant advances have been made in recent years in the size and complexity of deterministic problems that can be solved with these planners. However, in real problems, unexpected events may occur, actions may have unexpected outcomes, and the state of the world may not be known with certainty. If a deterministic planner is used to solve such problems, the execution of the plan may fail because the plan does not take into account the possible contingencies. Traditional approaches to planning under uncertainty involve Markov Decision Processes, which generates robust plans, but have high computational overhead. Other approaches to planning under uncertainty use contingency planning, translation into deterministic planning, or determinization and replanning. In recent years, planning-based solutions have been also used to solve goal recognition problems. Goal recognition may be seen as the inverse of planning since it is concerned with inferring an agent’s goals given some or all agent’s performed actions. There are few planning-based approaches for goal recognition, but this paradigm is still in its infancy. The previous paradigms all have one thing in common: the dominant techniques to solve their problems involve heuristic functions to guide the planning search. For this reason, in this thesis, we investigate classical heuristics that deal with action costs and introduce a novel domain-independent heuristic function that computes more accurate estimates of cost and estimates of probability. The approach involves a propagation of cost or probability plus Interaction information through a plan graph. This heuristic guides a classical planner to low-cost solutions, guides a probabilistic planner to high probability of success solutions, and rapidly solves goal recognition problems