Situated Planning with Soft Goals (Extended Abstract)

Abstract

Situated planning addresses the case in which an agent needs to achieve goals in a dynamic world where opportunities may be fleeting, and thus planning time must be taken into account during the planning process. For example, planning to take a bus must be completed in time to get to the bus stop. Previous work has focused on maximizing the probability of finding a plan that is still feasible at the time planning completes. In this paper, we consider the more realistic case in which each goal is optional and carries a reward. This setting, known as planning with soft goals, is challenging because every state is a goal state, and a heuristic estimate of the distance to go should consider many possible combinations of achievable goals. Furthermore, in our situated setting, the planner should take into account the estimated feasibility of actually finding a plan for a goal set in time. Unlike previous work on situated planning, where the planner can stop when it finds a feasible plan, the planner may be better off continuing to search for a better plan. In addition, the planner must also decide when to commit to one of the plans it has discovered. We present a metareasoning approach based on computing multiple temporal relaxed planning graphs and estimating the expected utility of searching for a better plan. This work extends the use of automated planning to the all-too-common case in which one has too much to do and not enough time to do it.