局部满意的启发式搜索算法

Heuristic Search for Partial Satisfaction Algorithm

在经典规划中,目标是找到一系列连续的行为,改变初始状态Z到一些满意的目标状态G.局部满意规划(PSP)问题是规划问题中的核心问题之一.在PSP中,文献[1-2]给出的每个目标有一个功能值ug≥0,代表每个目标对于用户的价值;每个行为a∈A,有一个关联执行代价Ca≥0,代表它执行每个行为的代价.P为所有有效规划集,Gp∈G为目标集,目标是寻找一个规划p在功能ug和执行代价之间寻找最大差,即arg p∈P max sum (ug)from g∈Gp-sum (Ca) from c∈p针对局部满意问题,提出了一种新的启发式搜索算法.该算法经过验证,取得了明显的效果.

In classical planning,the aim is to find a sequence of actions that transforms a given initial state Z to some state satisfying goals G.Partial satisfaction planning is one of key point in planning problem.In partial satisfaction planning,each goal has a utility value ug≥0,representing how mach each goal is worth to a user;each action a∈A has an associated execution cost Ca≥0,representing how costly it is to execute each action.Let P be the set of all valid plans and let Gp∈G be the set of goals achieved by a plan.The objective is to find a plan P that maximizes the difference between total achieved utility u and total cost of all actions： arg p∈P max sum （ug）from g∈Gp-sum （Ca） from c∈p.This article gives a new heuristic search algorithm for partial satisfaction planning.It confirms their effective through the examples.