多主体规划领域的逻辑建模及规划方法

摘要

要构建一个实际应用的多主体规划系统往往是一个非常复杂的工作。我们需要对系统进行建模，抽象出核心的要素，简化许多不需要的因素。然后在这种抽象的模型上讨论系统的性质和系统构建方法。为了描述一般规划领域特别是多主体规划领域，建立一个比较完整的形式系统是必要的。但形式系统应该简单，有充足的表达能力，适合对动作和变化等动态特性的逻辑推演，有良好的计算特性。在这样的形式系统中，对于多主体特性的引入不应该过多地增加建模复杂性和计算复杂性。另外，这种形式系统应该支持多种规划特性，如不确定性、扩展目标、分布规划、规划分解与合成、部分可观察性等等。而且该系统上应该能够构造有效的规划相关算法。 为了构建多主体规划应用系统，本文讨论了一般规划领域描述和动作推演的基础逻辑系统(动作理论)的建立，讨论了基于基础动作理论的多主体规划领域描述与建模的基本框架，讨论了基于该基本框架的规划方法，讨论了基于该基本框架的规划领域缩减与扩展方法。最后讨论了基于该框架的多主体规划系统的实现技术与方法。 方法总结如下： (1)对于规划领域描述及其推演系统，我们建立了基于动态逻辑的动作理论。它适合一般规划领域和多种规划特性的描述和推理。我们首先分别对命题动态逻辑和一阶动态逻辑扩展了动作的并行合成，其基本思想是用串行的形式来解释并发的动作，证明了形式系统的决定性质和计算性质，给出了公理化系统。然后，我们采用了完备集的构造方法解决frame问题和利用因果公理解决ramification问题，建立了一般的规划描述理论。最后我们把规划问题的基本求解归结到规划领域的模型检测上。 (2)基于建立的动态逻辑动作理论，我们采用分类动作标记方法，建立了多主体规划领域描述的框架。其基本思想是不在规划基础理论中引入多主体描述，而仅在规划领域描述时附加多主体信息。这些信息对于基础动作理论是无语义的，但这些信息可以直接应用于规划生成算法、规划的执行环境和规划协调控制机制中。另外，我们用基于模型的方法给出了一个一般化的规划生成算法，再基于分类动作信息，可以构成多种多主体规划情景的规划生成、执行和协调的策略与方法。 (3)为了验证我们的理论与方法，我们设计了多主体规划领域的描述语言maPDDL，它采用了基于系统变量的描述方法。并且基于领域语义模型的构造、优化和反向搜索的算法实现了它的规划器。 论文的主要成果包括并行命题动态逻辑和并行一阶动态逻辑相关的结论，frame问题和ramification问题的解决方案，分类动作的多主体领域描述方法，基于模型的通用规划生成、优化、执行和协调算法，maPDDL多主体规划领域描述语言及其规划器的实现方法。 论文的主要结论是：(1)并行动态逻辑有比多数其它系统更好的动态描述能力且更好的计算特性，其串行化的并行语义使其应用于系统建模时更直观和简单；(2)我们的frame问题的解决方法相比其它的方法，但给出了更为直观和简易的形式，这使得规划领域描述的模型构造变得简单直观；(3)分类动作的描述策略简化了多主体规划领域描述的复杂性和算法的复杂度，使得领域建模和规划生成等相对于传统领域没有直接增加复杂度，支持了多主体规划领域的多种情景要求；(4)基于模型的规划算法非常有效而且具有更一般的特性，适合于传统和多主体规划领域的多种特性要求；(5)maPDDL规划描述语言及其规划器可以成为一般、实用和有效的规划工具。

目录

文摘

英文文摘

论文说明：图表目录

声明

致谢

第一部分 背景和基础研究 Background and Fundamental Researches

第一章 概述 Overview

1.1问题陈述 Problem Statement

1.2举例 Examples

1.3研究工作小结 Summary of Approach and Results

1.4章节安排 Overview of the Contents

第二章 背景与相关研究工作 Background and Related Works

2.1动作理论 Action the Ories

2.2多主体规划 Multi-agent Planning

2.3基于模型检测的规划 Planning Via Model Checking

2.4评注与小结 Summary

第三章 并行命题动态逻辑 Parallel Proposition Dynamic Logic

3.1 引言 Introduction

3.2 PaPDL 的句法 Syntax

3.3 PaPDL的语义Semantics

3.4决定性和复杂性 Decidablility and Complexity

3.5 PaPDL表达能力的简单讨论 Expressiveness

3.6小结 Summary

第四章 并行一阶动态逻辑 Parallel Predicate Dynamic Logic

4.1 PaFDL 的句法 Syntax

4.2 PaFDL的语义Semantics

4.3 PaFDL的表达能力Exeressiveness

4.4 PaFDL的公理化 Axionmatization

4.5小结 Summary

第五章 基于动态逻辑的动作理论 Action Theory Based on Parallel Dynamic Logics

5.1 PaPDL的分支时态语义 Tempopal Semanticsof PaPDL

5.2 PaPDL规划领域描述Planning Domain Description

5.3 PaFDL的分支时态语义 Temporal Semantics of PaFDL

5.4Frame问题和Ramification问题 Frame and Ramification Problems

5.5规划问题及其规划解 Planning Problem and Its Solutions

5.6 Frame公理扩展的合理性分析 Notes on Frame Extenston

第二部分 多主体规划领域建模与分析 Multi-agent Planing Domain Modeling and Analysis

第六章多主体规划的领域建模 Modeling Multi-agent Planing Domain

6.1多主体规划领域描述框架 Framework for Multiagent Planning Domain Description

6.2分类动作 Sorted Actions

6.3多主体规划领域描述及其扩展领域模型构造Multi-agent Planning Domain Description and its Model Construction

6.4规划领域特性的考虑Domain Characteristics

6.5全局规划生成与分解 Planing for Multi-agent

6.6抽象规划与分布规划 Planning by Multi-agent

6.7规划执行Plan Execution

6.8动态分布连续规划 Distribu the Contionual Planning

6.9系统漂移时适应性规划的生成 Plan Generation for System Drift

第七章多主体规划领域的缩减与扩展 Multi-agent Planning Domain Reduction Andextension

7.1并发性扩展 Concurrency Extension

7.2抽象动作扩展与层次规划 Abstract Action Extension and Hierarchical Planning

7.3基于领域约束的模型缩减 Domain Reduction by Domain Constraints

7.4领域缩减的实际意义 Practical Implicitation of Domin Reduction

7.5基于规划约束的规划算法 Algorithm Based on Plan Constraints

7.6主体间交互的表示 Interaction Among Agents

第三部分 多主体规划系统 Multi-agent Planning System

第八章 多主题规划领域描述语言 maAPDDL Multi-agent Planning Domain Descripionlanguagae

8.1概述 Overview

8.2 maPDDL的句法及其直观语义 Syntax and Intuitive Semanics

8.3 maPDDL的形式语义Formal Semantics of ma PDDL

8.4基于maPDDL系统建模 Mooeling With maPDDL

8.5规划领域实例PLannimng Domain Examples

第九章 基于模型检测的maPDDL规划器maPDDL Planner Based on Model Checking

9.1基于NuSMV的规划器实现Planer Implementation Based on NuSMV

9.2 maPDDL的SMV转换语义 Tarlementation Semantics of maPDDL

9.3规划相关算法的实现 Implementation of Planning Algorithms

9.4规划领域模拟验证Planning Domain Simulation

9.5多主体规划系统构建 Building Multi-agent Planning Systems

9.6规划实例测试(Planning Examples)

9.7扩展模型构造算法实例测试 Extended Model Construction Testing

9.8通用规划算法实例测试 Universal Plan Generation Testing

9.9小结 Summary

第十章 部分可观察性及其在Ad Hoc网络路由的应用 Partial Observability and Iitsappliction in Ad Hoc Network Routing

10.1引言 Introduction

10.2部分可观察性的描述 Describing Partial Observability

10.3强规划的生成Strong Plan Generation

10.4实例：Adhoc移动网络的动态路山问题Case Study

10.5准确计时的可靠链路方法 Reliable Linking Through Accurate Timing

10.6效率分析 Performance Analysis

10.7实验测试与结果分析 Experiments and Results

第四部分 结论与进一步工作 Conclusion and Discussion

第十一章 贡献与结果 Contributions and Results

11.1并行动态逻辑 Parallel Dynamic Logics

11.2动作理论 Action Thecry

11.3多主体规划领域描述 Multi-agent Planning Domain Description

11.4规划领域描述语言 Planning Domain Description Language

11.5结论 Conclusion

第十二章进一步的工作 Future Works

参考文献 Referemces

附录