Object Transition Sequences: A New Form of Abstraction for HTN Planners

This paper presents EMS, an implemented HTN planning algorithm using a novel form of abstraction. A plan is viewed as a set of dynamic objects taking part in sequences of transitions. EMS builds up plans using an Expand then Make-Sound cycle: a plan is built up by constructing and expanding a tree of networks at different levels of abstraction, where a network contains object transition sequences. A network is made sound by adjusting the pre and postconditions of all the object transition sequences it contains, and proving the sequence in between is sound. As new objects are discovered in the detailed levels of the hierarchically developing plan, the pre and postconditions of their transition sequences are passed up to a parent network in the; hierarchy which must then be made sound. The main benefits of EMS are that it processes an expressive, declarative input language based on object hierarchies; it is efficient in its reasoning, in that object transition sequences can be manipulated independently of objects of unrelated sorts, and reasoning about condition achievement is performed locally in a network; and it provides a clear, sound algorithm with the potential of application to complex applications.