基于自动推理技术的智能规划方法

对几种智能规划方法中利用的逻辑演绎与推理技术予以分析,分别介绍利用命题逻辑的基于可满足性的规划方法与规划系统,利用模态逻辑与析取推理的Conformant规划方法与规划系统,利用非单调逻辑的规划方法和利用模糊描述逻辑的Flexible规划方法,并结合国际规划竞赛和相关论文等的实验结论说明上述方法的有效性和可行性.最后,提出目前基于自动推理技术的智能规划方法所面临的挑战、可能的处理方法以及与之相关的研究热点与趋势.     

命题编码中公理的组合与设计

近年来,基于可满足性的规划方法研究逐渐成为智能规划研究领域中的热点。提出3种基于Graphplan的编码方式中公理的改进:动作互斥的部分放松、动作互斥的完全放松方法、添加框架公理。基于SATPLAN2006规划系统分别实现上述3种改进的编码方式,并对国际规划竞赛中选用的标准后勤域与积木世界域的问题样例予以测试,分析不同编码方式的编码规模与求解效率,验证了基于Graphplan编码方式的改进在绝大多数情况下是有效的。最后,实现基于状态的编码方式,并对上述两个域进行测试,比较约简动作与约简状态这两种极端方式的求解效率和编码规模。实验结果表明,在后勤域的某些问题上基于状态的编码方式比基于动作的编码方式有效得多。上述的改进策略表明,可根据问题域的特性等来考虑该问题最适宜哪些公理组合的编码方式,而不固定使用某种特定的编码方式。     

基于量化布尔公式的条件规划编码方式

介绍条件规划问题及其相关的求解系统,着重分析以逻辑为基拙的编码方式。针对基于量化布尔公式的转换方法进行详细分析,给出3种不同形式的量化布尔公式编码。最后,对这3种编码进行比较,分析基于命题逻辑公式与量化布尔公式这两种不同转换方式的优劣,讨论基于量化布尔公式的规划方法未来的研究方向和发展趋势。     

面向深空探测任务的实数遗传编码多星任务规划算法

针对面向深空探测任务的多星任务规划问题,综合考虑卫星对目标时间窗口、卫星姿态机动以及工作能耗等约束条件,建立了面向深空探测任务的多星任务规划问题模型,针对常规01编码在进行大规模卫星任务规划时,存在的编码长度过长等问题,提出了一种基于实数编码方式的遗传算法,以求解面向深空探测的多星任务规划问题.该算法采用了一种以目标为染色体的实数编码方式,相比传统的以时间窗口为染色体的01编码方式,缩短了染色体长度,可有效提高算法的求解效率.通过仿真算例分析,验证了基于实数编码的遗传算法对求解多星任务规划问题的正确性、合理性和有效性,并将其与基于传统01编码方式的遗传算法进行对比分析,其结果表明基于实数编码方式的遗传算法在寻优能力和计算速度上具有明显优势,这为求解面向深空探测任务的多星任务规划问题提供了一种新的思路和方法.     

一种约简动作变元的命题规划编码方式

基于动作的编码方式是2006年国际规划竞赛中著名的最优规划系统SATPLAN2006采用的一种基于约简状态变元的命题规划编码方式.依据基于动作的编码方式,提出一种基于约简动作变元的自动命题规划编码方式:基于命题的编码方式.首先分析构造新编码方式的理论依据,提出基于命题的编码方式的编码组成,证明其有效性,并描述某些公理的具体实现细节,最后分析其与已有几种编码方式的不同之处.在SATPLAN2006中实现了基于命题的编码方式,利用国际规划竞赛选用的标准测试问题予以测试,并分析其与基于动作的编码方式等两种极端编码方式的求解特性.实验结果表明:对于顺序规划问题域,基于命题的编码方式更有效,而对于并发规划问题域,基于动作的编码方式更有效.     

Conformant规划的编码方式研究

以智能规划领域中的Conformant规划为研究对象,对几种Conformant规划中的编码方式予以综述;分别介绍了基于K（P）的编码方式、基于KT,M（P）的编码方式、基于Ki（P）的编码方式、基于d-DNNF的编码方式和CF2SAT编码方式。通过对几种编码方式的分析,说明基于转换思想的编码方式在Conformant规划中的作用,探讨其相关的研究热点和趋势。     

智能规划中的动作互斥编码方式研究

以规划领域中的动作为对象,研究规划方法中的动作互斥编码方式。介绍基于规划图的动作互斥编码、利用提取领域相关信息生成动作效果的直接阻碍与间接阻碍编码,以及依赖于域转移图动作间的长距离互斥编码,说明每类动作互斥编码的构造方法及其削减搜索空间、提高求解效率的作用。     

基于命题可满足性的经典最优规划方法

基于Graphplan的编码方式是2006年国际规划竞赛中著名的最优规划系统SATPLAN2006采用的编码方式。首先给出与编码相关的概念与性质,在基于Graphplan的编码方式的基础上,设计一种新的编码方式:基于FA的编码方式,并从理论上证明该编码方式的有效性。设计并实现对应的规划系统FA-SP,利用国际规划竞赛选用的Benchmark问题予以测试。实验结果表明,与SATPLAN2006相比,FA-SP对于所测两类规划域编码规模均有所压缩,除个别问题外求解效率都有一定程度的提高;对于顺序规划域Blocks World,编码规模平均压缩了40%,求解效率平均提高了2倍;对于并发规划域Logistics,带有小于5%的框架公理的FA编码规模平均压缩了75%,求解效率也有不同程度的提高。     

多阶段多产品调度问题的链式智能体遗传算法

将遗传算法的编码方式与智能体系统的演化结构相结合,提出一种求解多阶段多产品调度问题的链式智能体遗传算法.算法采用基于订单序列的编码方式,采用一种新的后向指派规则实现编码和可行调度间的一一对应.通过各智能体与其邻域环境的竞争与合作以及自身的自学习操作实现种群的演化过程.对多阶段多产品调度问题的仿真结果表明:链式智能体遗传...     

基于预测编码的样本自适应行动策略规划

军事行动、反恐突击等强对抗场景中,实时信息的碎片化、不确定性对制定具有博弈优势的弹性行动方案提出了更高的要求,研究具有自学习能力的智能行动策略规划方法已成为编队级强对抗任务的核心问题.针对复杂场景下行动策略规划状态表征困难、数据效率低下等问题,提出了基于预测编码的样本自适应行动策略规划方法.利用自编码模型压缩表示任务的原始状态空间,通过任务环境的状态转移样本,在低维度状态空间中使用混合密度分布网络对任务环境的动态模型进行学习,获得了表征环境动态性的预测编码;基于预测编码展开行动策略规划研究,利用时间差分敏感的样本自适应方法对状态评估值函数进行预测,改善了数据效率,加速了算法收敛.为了验证算法的有效性,基于全国兵棋推演大赛机机挑战赛的想定,构建了包含大赛获奖选手操作策略的5种规则智能体,利用消融实验验证编码方式、样本采样策略等不同因子组合对算法的影响,并使用Elo评分机制对各个智能体进行排序;实验结果表明:基于预测编码的样本自适应算法——MDN-AF得分排序最高,对战平均胜率为71%,其中大比分获胜局占比为67.6%,而且学习到了自主波次划分、补充侦察策略、“蛇形”打击策略、轰炸机靠后突...     

Knowledge forgetting: Properties and applications

In this paper we study a formal notion of knowledge forgetting in S5 modal logic. We propose four postulates and prove that these postulates precisely characterize both semantic and logical properties of knowledge forgetting. We then investigate possible applications of knowledge forgetting in various epistemic reasoning scenarios. In particular, we show that different forms of knowledge updates may be represented via knowledge forgetting. We also demonstrate how knowledge forgetting can be used in formalizing and reasoning about knowledge games with bounded memory.     

Epistemic Logic for Rule-Based Agents

The logical omniscience problem, whereby standard models of epistemic logic treat an agent as believing all consequences of its beliefs and knowing whatever follows from what else it knows, has received plenty of attention in the literature. But many attempted solutions focus on a fairly narrow specification of the problem: avoiding the closure of belief or knowledge, rather than showing how the proposed logic is of philosophical interest or of use in computer science or artificial intelligence. Sentential epistemic logics, as opposed to traditional possible worlds approaches, do not suffer from the problems of logical omniscience but are often thought to lack interesting epistemic properties. In this paper, I focus on the case of rule-based agents, which play a key role in contemporary AI research but have been neglected in the logical literature. I develop a framework for modelling monotonic, nonmonotonic and introspective rule-based reasoners which have limited cognitive resources and prove that the resulting models have a number of interesting properties. An axiomatization of the resulting logic is given, together with completeness, decidability and complexity results.     

智能主体的信念认知时态子结构逻辑模型*

智能主体获取信念的途径主要有两种：一种为他省,通过外界交互,从其他主体获取信息;另一种为自省,通过自己的历史数据库获取相关知识。对于主体信念的描述与刻画,两种途径缺一不可,但当前的BDI理论模型中较多地为他省系统,没有做到两者相结合。其次,在当前的许多理论模型中,通常使用的是二值逻辑、经典模态逻辑或其变形系统,使得相应的逻辑系统普遍存在逻辑全知和粗精度刻画等问题。针对上述问题进行了相关研究,采用了认知时态子结构逻辑建模的方法,表达了智能主体获得“双省”信念的方式,针对其建立了相应的逻辑系统BSoET。     

Minimal Belief and Negation as Failure in Multi-Agent Systems

We propose an epistemic, nonmonotonic approach to the formalization of knowledge in a multi-agent setting. From the technical viewpoint, a family of nonmonotonic logics, based on Lifschitz's modal logic of minimal belief and negation as failure, is proposed, which allows for formalizing an agent which is able to reason about both its own knowledge and other agents' knowledge and ignorance. We define a reasoning method for such a logic and characterize the computational complexity of the major reasoning tasks in this formalism. From the practical perspective, we argue that our logical framework is well-suited for representing situations in which an agent cooperates in a team, and each agent is able to communicate his knowledge to other agents in the team. In such a case, in many situations the agent needs nonmonotonic abilities, in order to reason about such a situation based on his own knowledge and the other agents' knowledge and ignorance. Finally, we show the effectiveness of our framework in the robotic soccer application domain.     

Conformant plans and beyond: Principles and complexity

Conformant planning is used to refer to planning for unobservable problems whose solutions, like classical planning, are linear sequences of operators called linear plans. The term ‘conformant’ is automatically associated with both the unobservable planning model and with linear plans, mainly because the only possible solutions for unobservable problems are linear plans. In this paper we show that linear plans are not only meaningful for unobservable problems but also for partially-observable problems. In such case, the execution of a linear plan generates observations from the environment which must be collected by the agent during the execution of the plan and used at the end in order to determine whether the goal had been achieved or not; this is the typical case in problems of diagnosis in which all the actions are knowledge-gathering actions.Thus, there are substantial differences about linear plans for the case of unobservable or fully-observable problems, and for the case of partially-observable problems: while linear plans for the former model must conform with properties in state space, linear plans for partially-observable problems must conform with properties in belief space. This differences surface when the problems are allowed to express epistemic goals and conditions using modal logic, and place the plan-existence decision problem in different complexity classes.Linear plans is one extreme point in a discrete spectrum of solution forms for planning problems. The other extreme point is contingent plans in which there is a branch point for every possible observation at each time step, and thus the number of branch points is not bounded a priori. In the middle of the spectrum, there are plans with a bounded number of branch points. Thus, linear plans are plans with zero branch points and contingent plans are plans with unbounded number of branch points.In this work, we lay down foundations and principles for the general treatment of linear plans and plans of bounded branching, and provide exact complexity results for novel decision problems. We also show that linear plans for partially-observable problems are not only of theoretical interest since some challenging real-life problems can be dealt with them.     

Possible events, actual events, and robots

To plan means reasoning about possible actions, but a robot must also reason about actual events. This paper proposes a formal theory about actual and possible events. It presents a new modal logic as a notation for this theory and a technique for planning in the modal logic using a first-order theorem prover augmented with simple modal reasoning. This avoids the need for a general modal-logic theorem prover. Adding beliefs to this theory raises an interesting problem for which the paper offers a tentative solution.     

Agent的意图模型

意图是Agent的一个不可缺少的意识属性,在决定理性Agent的行为时起着重要的作用.已经有了若干种基于正规模态逻辑的意图模型,但它们存在着严重的“逻辑全知”问题.该文阐明意图不是正规模态算子,并提出了另一种意图模型,它不存在“逻辑全知”问题和其他相关问题(例如,副作用问题等).这种意图模型与Konolige和Pollack的意图模型相比,比较简单、自然,且满足K公理和联合一致性原理,实际上,为非正规模态算子基于正规可能世界的语义表示提供了一种新的方法.