Robust Planning in Uncertain Environments
This work addresses robust planning for AI systems in uncertain domains, but it appears incremental as it builds on decision theory and existing planning methods.
The paper tackles planning in uncertain environments by developing an algorithm that computes conditional plans of maximum expected utility, demonstrating through experiments in a blocks world domain that a robustness factor effectively controls risk-aversion in the plans.
This paper describes a novel approach to planning which takes advantage of decision theory to greatly improve robustness in an uncertain environment. We present an algorithm which computes conditional plans of maximum expected utility. This algorithm relies on a representation of the search space as an AND/OR tree and employs a depth-limit to control computation costs. A numeric robustness factor, which parameterizes the utility function, allows the user to modulate the degree of risk-aversion employed by the planner. Via a look-ahead search, the planning algorithm seeks to find an optimal plan using expected utility as its optimization criterion. We present experimental results obtained by applying our algorithm to a non-deterministic extension of the blocks world domain. Our results demonstrate that the robustness factor governs the degree of risk embodied in the conditional plans computed by our algorithm.