Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/758

On measuring plan quality

Authors Lin, Fangzhen
Issue Date 1998
Source Proc. of the Sixth Int. Conf. on Principles of Knowledge Representation and Reasoning (KR"98), Trento, Italy , June 1998, p. 224-233
Summary By using an example from a robot navigating domain we argue that to specify declaratively the behavior of an agent, we need to have a formal and explicit notion of "quality plans". To that end, we propose the following three domain independent measures of plan quality: a plan is said to be A-minimal if none of the actions in it can be deleted and have it continue to be a plan; it is said to be B-minimal if none of its segments can be deleted and have it continue to be a plan; and it is said to be C-minimal if none of its segments can be replaced by a single action and have it continue to be a plan. We show that given a plan, checking if it satisfies any of these three measures, and if not transforming it into one that does, can be done in polynomial numbers of plan tests. We also show how these three notions of plan minimality can be axiomatized naturally and straightforwardly in the situation calculus and, as a result, show their relationships with STRIPS triangle tables. Finally, we show their applications in the declarative specifications of agents' behaviours
Subjects
Language English
Format Conference paper
Access
Files in this item:
File Description Size Format
kr98.pdf 207871 B Adobe PDF