图规划框架下的可能性规划的研究与实现

【作者】 殷明浩；

【导师】 谷文祥；

【作者基本信息】 东北师范大学 ， 计算机软件与理论， 2004， 硕士

【摘要】 经典智能规划多是在强约束假设条件的基础上建模的，例如要求规划agent对于动作的结果的知识完全，且规划agent执行动作的结果是确定的，从而不能运用于大多数实际系统和实际领域中。本文的目的在于利用可能性理论描述规划动作的不确定性，使得可能性理论在规划建模中得以运用。由于可能性理论利用模糊集合理论来描述知识，相对于利用概率方法对规划的不确定性采用定量描述方法，可能性描述规划的不确定性采用的是定性描述的方法；因而即使规划agent对于规划的不确定性缺乏精确的评估标准的时候，依然可以找到一条最优规划。同时由于可能性方法在描述无知方面相对于概率方法更为优秀，我们认为可能性智能规划相对于概率智能规划在描述动作的不确定性上有着更大的优势。本文在给出可能性动作，可能性智能规划的相关定义后，证明了经典的智能规划是可能性规划的特例，因而凡是适合于求解可能性规划的方法都可以运用于经典规划求解中。但是相对于经典规划而言，可能性智能规划规划表示能力更强，更易于适用于实际系统。同时我们可以看到，在过去十年中，规划图算法无论在经典规划领域还是在概率规划领域都取得了巨大的成功。本文在规划图算法的框架下给出了一种求解最优可能性规划的算法，并给予实现。实验证明我们的规划方法是稳健高效的。更多还原

【Abstract】 Classical approaches of intelligent planning are based on strong assumptions such as: the agent has total knowledge of planning domains, or the effects of the agent’s action are deterministic. So they can’t be applied to most practical systems.The aim of the paper is to advance a possibility theory based planning method. Using possibility distribution to describe the uncertainty of the agent’s effects, the function of our planning algorithm is more powerful and more adaptable. Though traditional methods in non-deterministic planning are based on probability theory, we believe our method is better because possibility theory is more powerful in handling ignorance. So even when we can’t offer a precise scale on the uncertainty of the agent’s effects, our method can also work. In this sense, our method is qualitative rather than quantitative. After introducing the concepts of possibilistic actions, possibilistic plans, we introduce a graphplan based method. Using this method, we can find an optimal plan in a given time window. What’s more, we also prove that classical plan is a special case of possibilistic plan. We have implemented our method in c++, and the experiment has shown that our method is efficient and robust.更多还原