Abstract
In this paper we present a sound and complete linear planning algorithm which accommodates conditional actions: actions whose effects cannot be predicted with certainty. Conditional linear planning is significantly simpler than conditional non-linear planning in conception and implementation. Furthermore, the efficiency trade-offs which favor non-linear planning do not necessarily carry over with the same force to planning with conditional actions. We have applied our conditional linear planner, Plinth, to the problem of planning image processing actions for NASA’s Earth Observing System. We discuss the extension of Plinth to probabilistic planning.