摘要
在经典规划中,目标是找到一系列连续的行为,改变初始状态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.
出处
《微电子学与计算机》
CSCD
北大核心
2011年第10期194-200,共7页
Microelectronics & Computer
基金
国家自然科学基金项目(60775045
61033013)
关键词
启发式搜索算法
局部满意规划
宽松规则
向前状态启发式搜索算法
heuristic search algorithm
partial satisfaction plan
loose rule
forward condition heuristic search algorithm