Solution to Plan Recognition Problem Based on Circumscription
Jiang Yun · Chinese Journal of Computers · 2002
Plan recognition is a new technique for planning field of artificial intelligence. Given a fragmented, impoverished description of the actions performed by one or more agents, we need the technique to infer a rich, highly interrelated description. A generalized formal plan recognition model presented by Kautz is the best famous method in plan recognition field at present. Kautz's model is under the assumptions that the agent has complete knowled1ge and does not make mistakes. Under these assumptions, plan recognition is similar to McCarthy's circumscription theory. We combine circumscription with plan recognition, and investigate plan recognition problem with circumscription. At first we present a definition of plan recognition and a formal formalization of plan, the formalization includes the relations among plans. Then we prove that the plan recognition's minimum plan set that is based on the observations is the same as the circumscription of the observations. At last we give an algorithm of computing the plan recognition's minimum plan set by circumscription. As circumscription is a second-order non-monotonic formulism, its mechanical computation is a very difficult problem. There is a method to turn a second-order circumscription into a set of first-order formulas. This kind of first-order formula can be computed directly with pointwise circumscription. This profits from two main works: a method prompted by Lifschitz, that under some restriction, second-order formula could be turned into first-order formula. Another kind of circumscription, pointwise circumscription not only is logically equivalent to second-order circumscription, but also could be defined in any first-order theories under some conditions, that is to say that it always behaves as a first-order approximation of second-order circumscription without exceptions. Because of pointwise circumscription's attractive feature, the method we given here can compute circumscription mechanically. The method resolves some problems in Kautz's method. The semantic of the method is direct and distinct due to the circumscription's good semantic property. The scope of the inferred plans can be adjusted through changing the values of the variables in the circumscription, and the computation is more simple and more flexible. The priorities in observations, which are offered by the priority pointwise circumscription, make the circumscription procedure pay more attention on those events that are more important or more special. It can reduce the inferring, and obtain the plans efficiently when there are more than one candidate. This method can enhance the ability of fault tolerance when agent makes mistakes. In other words, if there is not completed satisfied plan in system, the most similar one will be found.