Diagnosis and planning with resource constraints

Consider the task of selecting actions that move a complex physical system such as a spacecraft from its current state to a state that achieves a set of desired goals. In practice, this task is complicated by the possibility of failures. When failures occur, the system enters an unanticipated state and subsequent actions may not have the expected effect. The exact state of the system may not be directly observable, and some goals may become unachievable. Intuitively, we desire actions that move the system from states it's likely to occupy to a state that achieves all goals that remain achievable. This work consists of novel diagnosis algorithms for determining the likely states of a system even when failures are not immediately observable, and novel planning algorithms for achieving as many goals as possible even when the initial state of the system is not exactly known. If computation time is restricted, the quality of the diagnoses and plans produced degrades gracefully. Results are presented on examples from the domain of spacecraft control and the planning literature. The diagnosis algorithms generate approximate belief states for a relevant class of partially observable Markov decision processes with very large state spaces. The algorithms incrementally generate an approximate belief We efficiently maintain a partial belief state when it remains consistent with observations and revisit past assumptions about the system's evolution when required by delayed evidence of a failure. Conformant planning is the problem of generating a plan that moves a system from any of a number of possible initial states to a goal state. The dominant approach considers the effects of actions in all states simultaneously. In this work, we find a plan for one possible state and incrementally extend it to work in all states. We move beyond conformant plans to optimize the goals a plan achieves and the initial states it considers according to user priorities. Thus we find good plans even when no conformant plan exists due to system failures, or none can be found due to limited computation.