迁移工作流过程分解及其规划方法研究
|
摘要
迁移工作流是一类基于移动agent技术的工作流管理范型。在迁移工作流模型中,迁移实例是任务的执行主体,工作位置是迁移实例的运行场所。迁移实例携带任务、目标和数据在分布的工作位置之间迁移,利用工作位置所提供的服务执行任务并接受服务结果,无需每一步都通过中心工作流引擎来交换数据,从而将集中在中心引擎上的控制逻辑分散到各迁移实例；迁移实例在执行任务过程中,能够根据环境的变化自治地决策迁移动作,当发现当前的工作位置不能满足其执行要求时,迁移实例将迁移到另一个能满足其要求的工作位置上继续执行；除迁移时间外,迁移实例的工作过程无需依赖网络连接。因此,迁移工作流模型大大提高了工作流系统适应动态环境的灵活性,特别适合那些执行环境动态多变和需要大量调用远程服务的分布式业务并发处理过程。
迁移工作流技术的实质是利用迁移实例的群体智能实现工作流的整体执行目标,其核心是多迁移实例路径规划问题,即确定如何对任务进行有效分配,并根据执行环境生成满足执行目标的位置序列。按照智能规划思想,迁移实例的路径规划主要包括过程分解、个体路径规划和群体路径规划三个关键步骤。过程分解的目标是生成符合迁移实例执行特征,且覆盖整个任务集的过程分支的集合,每个过程分支包含任务序列与执行目标；基于过程分解结果,迁移实例个体路径规划将给出在动态不确定的执行环境下,采用何种方法选择工作位置来执行所分配的任务序列并达到预期的执行目标；群体路径规划基于个体路径规划,同时要考虑迁移实例之间的群体协作,即：迁移实例为实现群体目标而进行的个体目标协调,包括迁移实例之间组织结构、冲突消解策略以及通信协议等。
本文基于山东大学移动计算实验室自行研发的迁移工作流管理系统框架,结合国家自然科学基金课题“面向目标的迁移工作流方法研究”,对迁移工作流执行系统的两个关键问题：业务过程分解和迁移实例路径规划进行了系统的研究,内容涵盖：基于极大覆盖子树的工作流过程域分解、面向多层次主从结构的业务过程并行分解、过程分支的静态规划、面向不确定执行环境的迁移实例个体在线路径规划和多迁移实例部分全局路径规划,并在原型系统平台上对上述工作进行了验证和分析。
本文工作的主要研究内容包括：
1.面向迁移实例群体协作的迁移工作流过程分解方法研究。
不同于基于RPC(Remote Procedure Call)的工作流过程分解,迁移工作流过程分解的目的是服务于迁移实例对业务过程的协同规划与执行,由于任务之间的关系决定了迁移实例之间的角色定位,因而业务过程的分解需要考虑任务分配后迁移实例的组织结构和协作方式。本文将迁移工作流过程分解划分为两个步骤：域分解和并行分解。域分解面向大规模业务过程,分解的目的是为了降低直接并行分解以及迁移实例群体协作的高复杂性。针对域分解,本文提出一种基于极大覆盖子树的过程分解算法。并行分解面向迁移实例的群体规划,将业务过程逐层分解为一组具有主从关联的过程分支的集合,其分解方法是按任务粒度求解过程图的关键路径,然后逐层分离以关键路径遍历的过程分支,按树型结构形成过程分支之间的主从支配关系,并使之转化为迁移实例之间的协作关系。本文针对服务质量约束的工作流执行系统,分别给出了业务过程结构分解的算法和服务质量约束的分配算法,并对所生成的过程分支给出一种静态路径规划离散粒子群优化算法。
2.面向不确定执行环境的迁移实例个体在线路径规划方法研究。
对于不确定的执行环境,迁移实例在工作过程中难以做出一个整体的路径规划,只能根据当前执行环境的状况采取阶段性寻优的规划方式。本文基于Markov决策过程(Markov Decision Process, MDP)建模时间约束的迁移实例个体在线路径规划,以任务划分执行阶段,以剩余执行时间、时间临界度、时间偏移度和规划深度为状态变量,在每个执行阶段,迁移实例根据当前环境的动态性确定一个规划窗口,在当前规划窗口内求解满足约束的最优迁移路径。由于规划深度(规划窗口的大小)取决于执行环境的不确定程度,因而需要一种对执行环境不确定性的度量方法。本文借鉴信息熵的概念,提出一种通过周期采样计算工作位置服务质量稳定性熵和服务数量稳定性熵的方法,并基于工作位置的服务稳定性来度量执行环境的不确定性,然后根据环境的不确定性设置规划深度。实验表明,该方法既具有良好的动态环境适应性,又兼顾了整体路径规划的长远性。
3.面向群体协作的迁移实例部分全局路径规划方法及其体系结构研究。
在大规模迁移工作流管理系统中,业务过程通常由多个迁移实例协同完成。由于个体路径规划仅关注迁移实例自身目标的优化实现,缺少迁移实例之间的通信与协商,因而不能保证生成路径的全局最优性。本文基于部分可观察Markov决策过程(Partially Observable Markov Decision Process, POMDP)建模多迁移实例部分全局路径规划,提出一种迁移实例部分全局规划两层体系结构,将群体路径规划问题划分为协作层和个体规划层,其中,协作层面向群体协作,关注迁移实例的组织方式、冲突消解策略以及迁移实例之间的通信协商,其目标是通过协商确定个体规划的执行目标,而不需要考虑对每个任务的规划细节；个体规划层则针对协作层制定的个体执行目标,关注该目标的实现方法,而无需考虑群体协作问题。在个体规划层,采用个体在线路径规划方法；在协作层,本文给出了一种迁移实例的树型组织结构,基于该结构提出了一种迁移实例的协作通信协议以及服务冲突和目标冲突的消解策略与实现方法。这种分层规划的思想有效地简化了迁移实例群体规划的复杂性,为多智能体的协同计算在工作流技术中的应用提供一种有价值的探索。
本文工作的创新点主要体现在：
1.提出了一种基于多层次主从结构的结构化业务过程并行分解方法。
不同于中心化WfMC模型的分解,迁移工作流过程分解的核心是如何支持非中心化的迁移实例有序协作。本文提出的基于多层次主从结构的迁移工作流过程并行分解方法,以树型结构表示过程分支之间的主从关系,以过程分支中的同步任务为协作关键点。因为在任务指派之后,过程分解树可以等价地映射为迁移实例组织树,所以,迁移实例可以基于过程分支之间的主从关系和协作关键点实现按需协商,使协作有序。与不区分主从关系的分解方法相比,树形结构表示的主从关系能够提供更加清晰的协作线索,有效支持迁移实例之间的自主协作。
2.提出了一种基于MDP和不确定执行环境的迁移实例在线路径规划方法。
不同于已知全局环境的路径规划方法,迁移实例在线路径规划的核心是如何度量执行环境的不确定性并采取相应的行为策略。本文提出的基于MDP和不确定执行环境的迁移实例在线路径规划方法,以服务稳定性熵度量执行环境的不确定性,以规划窗口为行为策略,与基于贪心策略的一步规划方法相比,基于环境不确定性度量的规划窗口方法,既具有对不确定性执行环境的动态适应性,又兼顾了整体规划的长远性。
3.提出了一种基于POMDP的多迁移实例部分全局路径规划方法。
除业务过程分解方法必须支持迁移实例有序协作外,迁移实例群体规划的另一个目标是如何简化群体规划的复杂度,提高业务过程的执行效率。本文提出的基于POMDP的迁移实例部分全局路径规划方法,以同步任务划分全局规划的执行阶段,以基于同步任务划分的任务帧为个体规划单元,全局规划实现目标在协作迁移实例之间的分配,部分规划实现迁移实例基于任务帧和目标分配的路径构建。与不分层的群体规划方法相比,由协作层和个体规划层组成的体系结构可以有效降低迁移实例群体路径规划的实现复杂度,提高个体规划在实现方法上的灵活性。
本文所提出的迁移工作流过程分解与规划方法在仿真实验和应用实例中已得到验证,但迁移工作流的群体规划是一个复杂的问题,还有很多值得探索和改进的方面,进一步的研究工作包括：
1.业务过程在线分解与任务合并方法。对于复杂和多变的执行环境,单纯的事前分解可能使过程分支粒度的适应性不够,因此,如何支持迁移实例对业务过程的在线分解与任务合并具有非常实际的意义。在以后的研究中,应考虑将过程分解纳入迁移实例在线路径规划中,以实现动态执行环境下的业务过程按需分解。
2.非结构化业务过程分解与群体路径规划方法。本文以结构化业务过程为研究对象,而非结构化业务过程分解与群体路径规划问题还需要在本文基础上做进一步的研究,下一步的工作将包括对非结构化业务过程并行分解算法的改进和群体规划体系结构的扩展等。
Migrating workflow is a workflow management paradigm based on mobile agent technology. In a migrating workflow system, a migrating instance(MI) acts as the task executer. It catches the task list and data with an execution objective, migrates from one workplace to another, utilizes the service provided by the workplaces and accepts the service results, without needing to exchange data with the workflow management engine. By this way, the control flow that concentrated in the center engine can be decentralized to the migrating instances. During the execution period, a migrating instance will determine its routing path according to the dynamic execution environment. When the migrating instance finds that the current workplace can not meet its requirements to execute the task, it will migrate to another available workplace and go on. Except for migrating time, the migrating instance does not depend on the reliability of network connection. Therefore, migrating workflow model greatly improves the adaptability to the dynamic execution environment. Especially, the model adapts to those concurrent processes of distributed business that need large number of remote procedure call (RPC) in a changeful execution environment.
The essence of migrating workflow model is to utilize the swarm intelligence of migrating instances to achieve the overall workflow execution goal. The key issue is the migrating instance path planning, which is to assign the tasks to the migrating instances and plan the optimal actions according to the specific execution environment so as to achieve the execution objective. According to the planning idea of AI, the path planning of migrating instances mainly consists of three key issues: process partition, individual path planning and group planning with multi migrating instance cooperation. The purpose of process partition is to separate a workflow process into a set of sub-processes, each sub-process with a sequence of tasks and an expected goal will be assigned to a migrating instance. Based on the results of process partition, the individual path planning is to select a most suitable workplace sequence for the sub-process so as to reach its individual goal in a dynamic and uncertain environment. Based on the individual planning, the group planning will take into account the group cooperation among the migrating instances for the workflow global goal, which includes the organizational structure of migrating instances, communication protocols and conflict resolution strategies.
Supported by the National Natural Science Foundation of China "Research on the methods of goal-oriented migrating workflow", this thesis focuses on two issues: process partition and path planning based on the migrating workflow system framework proposed by the Mobile Computing Laboratory of Shandong University, which includes:process fragmentation based on the domain-cover sub-tree, process parallel partition method with a master-slave structure, static task planning for sub-processes, migrating instance individual planning with uncertain environment, and partial global planning. The study has been proved and analyzed on a prototype migrating workflow platform.
The main contributions of this work are described as follows.
1. Research on workflow process partition method for multi-leveled master-slave cooperation of the migrating instances.
Different from the RPC based workflow process fragmentation methods, the objective of process partition in a migrating workflow is to cater for the migrating instance group planning. Since the relations among the migrating instances are based on the relations between the sub-processes they catch, the collaboration relations among the migrating instances have been taken into account before partitioning. The process partition in this work consists of two steps, which are domain fragmentation and parallel partition. The former aims at large workflow process, with the purpose of reducing the high complexity of parallel partition and migrating instance group cooperation. This thesis proposes a maximum sub-tree based method which fragments a workflow process into a set of domain-processes. Each domain-process with a relative independent domain attribute will be parallel partitioned in the next step. The parallel partition is to divide a process or a domain-process into a set of task-sequences with master-slave relations among them. The main idea of parallel partition is that, repeatedly search for the critical path of DAG (or sub-DAGs) of the process, and then separate the obtained critical path from the DAG and the remained sub-DAGs until the process has been completely partitioned. The master-slave relations among the sub-processes generated by the parallel partition will become the relations among migrating instances. In order to meet the quality of service (QoS) constrain, this thesis studies not only the structure partition but also the QoS allocation methods, and presents a discrete particle swarm optimization algorithm for sub-process static path planning.
2. Research on migrating instance individual path planning in uncertain execution environments.
Since the execution environment is changeful and uncertain, it is hard for a migrating instance to make a long term planning. A feasible way is to take a periodic optimizing planning according to the specific environment. This thesis models the individual path planning problem with Markov decision process (MDP), which segments the stages by tasks and define the execution state variables as remain deadline, time offset and planning step length. In each stage, the migrating instance determines a planning window according to dynamic environment and searches for the optimal routing path which meets the QoS constraints. Since the planning step length depends on the uncertainty of execution environment, it is possible to give a measurement method for the uncertainty of execution environment. Thus we reference the concept of entropy and present an approach to calculate the stability entropy of a workplace by periodic sampling the change of the quality of service and quantity of service. Based on the stability entropy of the available workplaces, the uncertainty of the execution environment can be measured, which enable the migrating instance to set the planning step length in each stage. The experiment results prove that the proposed approach achieves the satisfactory trade-off between the adaptability to the environment and execution performance.
3. Research on partial global path planning for migrating instance group cooperation.
The objective of migrating instance individual path planning is to optimize its execution performance without considering the execution of its partners'. However, due to lack of the group cooperation, the migrating instance plans its routing path based only on the observations about environment by itself and care only about the objective of its own. So the planning strategy can be optimal for the migrating instance itself, but not for the global workflow. This thesis models the migrating instances group planning as a partially observable Markov decision process (POMDP), and proposes a partial global planning architecture that divides the group planning problem into two layers:cooperation layer and individual planning layer. The cooperation layer focuses on group cooperation, which includes the organization structure of migrating instances, conflict resolution principle and communication protocols. The goal of cooperation layer is to determine the individual planning objective for each task frame and does not have to handle the details of task planning. The individual planning layer focuses on the implementation of the objective obtained by the cooperation layer and does not have to care about the group cooperation. For the cooperation layer, we propose an MI cooperative organization based on tree structure. Based on this structure, we also put forward a set of communication protocols between the MIs, as well as the resolution principles and methods of service conflicts and objective conflicts. The two-layer partial global planning architecture provides a way to simplify the complexity of group planning problem, which offers a valuable resolution of multi-agent collaborative computing in the workflow management applications.
The main innovative contributions of this thesis are summarized as follows.
1. This thesis proposes a process parallel partition method with a multi-leveled master-slave structure.
Different from the process partition methods in a centralized workflow with WfMC model, the objective of process partition in a migrating workflow is to support the orderly cooperation among the migrating instances. The parallel partition method proposed in this thesis fragments a process into a set of task-sequences, in which the synchronization tasks are served as the cooperation ports. The master-slave relations among the task-sequences are expressed as a partition tree which can be equivalently mapped into an organization tree of migrating instances after task assignment. Based on the master-slave relations and cooperation ports, the migrating instances can achieve on-demand consultation and orderly cooperation. Compared with the partition approaches without master-slave relations, the partition tree makes the cooperation relations more clearly and thus can support the autonomous cooperation of migrating instances.
2. This thesis presents online path planning method for migrating instances based on MDP and uncertain execution environments.
Different from the path planning approaches with global execution environments, the key idea of the online path planning method proposed in this thesis is to measure the uncertainty of the execution environment and take actions according to this measurement. Referencing the concept of entropy, this thesis presents an approach to measure the uncertainty of the execution environment and enable a migrating instance to make actions within a planning window that is set based on the execution environment. So compared with the one-step greedy planning strategies, our method can find a way to achieve the satisfactory trade-off between the adaptability to the execution environment and the overall execution performance of the migrating workflow.
3. This thesis proposes a POMDP based method for migrating instances partial global path planning and puts forward a group planning architecture.
In addition to the process partition method that must support the group cooperation of migrating instances, the other objective of group planning is to improve the execution efficiency of the workflow process. The partial global path planning method proposed in this thesis is modeled based on POMDP, which segments the global planning stages by the synchronization tasks and makes the individual planning within a task frame. Task frames are generated by dividing a task-sequence with synchronization tasks. The group planning assigns the workflow overall goal to the migrating instances and the individual planning focuses on the implementation of the partial goal obtained in the group planning. Compared with non-layered group planning methods, the architecture with cooperation layer and individual planning layer can effectively reduce the complexity of migrating instances group planning and improve the flexibility of individual planning methods.
The migrating workflow process partition and planning methods proposed in this thesis have been testified in simulation experiments and application cases. However, the migrating instances group planning is a complex problem, so there are still many aspects to be improved. To further the research started in this thesis, we propose the following future works:
1. Methods to online process partition and task clustering. In a complex and changeful environment, a workflow process depends only on the pre-partitioning before execution, the adaptability of the partition granularity is insufficient. So the study of online process partitioning and task clustering will be practically useful. In the future work, we suggest adopting the process partition into the migrating instance online path planning so that a process can be dynamically partitioned on-demand.
2. Process partition and planning methods for unstructured workflows. This work is based on structured workflow, so there are still research aspects to be further studied in unstructured workflows, such as unstructured process parallel partition and group path planning. We should further improve on the process partition algorithm and the architecture of migrating instances group planning.
迁移工作流技术的实质是利用迁移实例的群体智能实现工作流的整体执行目标,其核心是多迁移实例路径规划问题,即确定如何对任务进行有效分配,并根据执行环境生成满足执行目标的位置序列。按照智能规划思想,迁移实例的路径规划主要包括过程分解、个体路径规划和群体路径规划三个关键步骤。过程分解的目标是生成符合迁移实例执行特征,且覆盖整个任务集的过程分支的集合,每个过程分支包含任务序列与执行目标；基于过程分解结果,迁移实例个体路径规划将给出在动态不确定的执行环境下,采用何种方法选择工作位置来执行所分配的任务序列并达到预期的执行目标；群体路径规划基于个体路径规划,同时要考虑迁移实例之间的群体协作,即：迁移实例为实现群体目标而进行的个体目标协调,包括迁移实例之间组织结构、冲突消解策略以及通信协议等。
本文基于山东大学移动计算实验室自行研发的迁移工作流管理系统框架,结合国家自然科学基金课题“面向目标的迁移工作流方法研究”,对迁移工作流执行系统的两个关键问题：业务过程分解和迁移实例路径规划进行了系统的研究,内容涵盖：基于极大覆盖子树的工作流过程域分解、面向多层次主从结构的业务过程并行分解、过程分支的静态规划、面向不确定执行环境的迁移实例个体在线路径规划和多迁移实例部分全局路径规划,并在原型系统平台上对上述工作进行了验证和分析。
本文工作的主要研究内容包括：
1.面向迁移实例群体协作的迁移工作流过程分解方法研究。
不同于基于RPC(Remote Procedure Call)的工作流过程分解,迁移工作流过程分解的目的是服务于迁移实例对业务过程的协同规划与执行,由于任务之间的关系决定了迁移实例之间的角色定位,因而业务过程的分解需要考虑任务分配后迁移实例的组织结构和协作方式。本文将迁移工作流过程分解划分为两个步骤：域分解和并行分解。域分解面向大规模业务过程,分解的目的是为了降低直接并行分解以及迁移实例群体协作的高复杂性。针对域分解,本文提出一种基于极大覆盖子树的过程分解算法。并行分解面向迁移实例的群体规划,将业务过程逐层分解为一组具有主从关联的过程分支的集合,其分解方法是按任务粒度求解过程图的关键路径,然后逐层分离以关键路径遍历的过程分支,按树型结构形成过程分支之间的主从支配关系,并使之转化为迁移实例之间的协作关系。本文针对服务质量约束的工作流执行系统,分别给出了业务过程结构分解的算法和服务质量约束的分配算法,并对所生成的过程分支给出一种静态路径规划离散粒子群优化算法。
2.面向不确定执行环境的迁移实例个体在线路径规划方法研究。
对于不确定的执行环境,迁移实例在工作过程中难以做出一个整体的路径规划,只能根据当前执行环境的状况采取阶段性寻优的规划方式。本文基于Markov决策过程(Markov Decision Process, MDP)建模时间约束的迁移实例个体在线路径规划,以任务划分执行阶段,以剩余执行时间、时间临界度、时间偏移度和规划深度为状态变量,在每个执行阶段,迁移实例根据当前环境的动态性确定一个规划窗口,在当前规划窗口内求解满足约束的最优迁移路径。由于规划深度(规划窗口的大小)取决于执行环境的不确定程度,因而需要一种对执行环境不确定性的度量方法。本文借鉴信息熵的概念,提出一种通过周期采样计算工作位置服务质量稳定性熵和服务数量稳定性熵的方法,并基于工作位置的服务稳定性来度量执行环境的不确定性,然后根据环境的不确定性设置规划深度。实验表明,该方法既具有良好的动态环境适应性,又兼顾了整体路径规划的长远性。
3.面向群体协作的迁移实例部分全局路径规划方法及其体系结构研究。
在大规模迁移工作流管理系统中,业务过程通常由多个迁移实例协同完成。由于个体路径规划仅关注迁移实例自身目标的优化实现,缺少迁移实例之间的通信与协商,因而不能保证生成路径的全局最优性。本文基于部分可观察Markov决策过程(Partially Observable Markov Decision Process, POMDP)建模多迁移实例部分全局路径规划,提出一种迁移实例部分全局规划两层体系结构,将群体路径规划问题划分为协作层和个体规划层,其中,协作层面向群体协作,关注迁移实例的组织方式、冲突消解策略以及迁移实例之间的通信协商,其目标是通过协商确定个体规划的执行目标,而不需要考虑对每个任务的规划细节；个体规划层则针对协作层制定的个体执行目标,关注该目标的实现方法,而无需考虑群体协作问题。在个体规划层,采用个体在线路径规划方法；在协作层,本文给出了一种迁移实例的树型组织结构,基于该结构提出了一种迁移实例的协作通信协议以及服务冲突和目标冲突的消解策略与实现方法。这种分层规划的思想有效地简化了迁移实例群体规划的复杂性,为多智能体的协同计算在工作流技术中的应用提供一种有价值的探索。
本文工作的创新点主要体现在：
1.提出了一种基于多层次主从结构的结构化业务过程并行分解方法。
不同于中心化WfMC模型的分解,迁移工作流过程分解的核心是如何支持非中心化的迁移实例有序协作。本文提出的基于多层次主从结构的迁移工作流过程并行分解方法,以树型结构表示过程分支之间的主从关系,以过程分支中的同步任务为协作关键点。因为在任务指派之后,过程分解树可以等价地映射为迁移实例组织树,所以,迁移实例可以基于过程分支之间的主从关系和协作关键点实现按需协商,使协作有序。与不区分主从关系的分解方法相比,树形结构表示的主从关系能够提供更加清晰的协作线索,有效支持迁移实例之间的自主协作。
2.提出了一种基于MDP和不确定执行环境的迁移实例在线路径规划方法。
不同于已知全局环境的路径规划方法,迁移实例在线路径规划的核心是如何度量执行环境的不确定性并采取相应的行为策略。本文提出的基于MDP和不确定执行环境的迁移实例在线路径规划方法,以服务稳定性熵度量执行环境的不确定性,以规划窗口为行为策略,与基于贪心策略的一步规划方法相比,基于环境不确定性度量的规划窗口方法,既具有对不确定性执行环境的动态适应性,又兼顾了整体规划的长远性。
3.提出了一种基于POMDP的多迁移实例部分全局路径规划方法。
除业务过程分解方法必须支持迁移实例有序协作外,迁移实例群体规划的另一个目标是如何简化群体规划的复杂度,提高业务过程的执行效率。本文提出的基于POMDP的迁移实例部分全局路径规划方法,以同步任务划分全局规划的执行阶段,以基于同步任务划分的任务帧为个体规划单元,全局规划实现目标在协作迁移实例之间的分配,部分规划实现迁移实例基于任务帧和目标分配的路径构建。与不分层的群体规划方法相比,由协作层和个体规划层组成的体系结构可以有效降低迁移实例群体路径规划的实现复杂度,提高个体规划在实现方法上的灵活性。
本文所提出的迁移工作流过程分解与规划方法在仿真实验和应用实例中已得到验证,但迁移工作流的群体规划是一个复杂的问题,还有很多值得探索和改进的方面,进一步的研究工作包括：
1.业务过程在线分解与任务合并方法。对于复杂和多变的执行环境,单纯的事前分解可能使过程分支粒度的适应性不够,因此,如何支持迁移实例对业务过程的在线分解与任务合并具有非常实际的意义。在以后的研究中,应考虑将过程分解纳入迁移实例在线路径规划中,以实现动态执行环境下的业务过程按需分解。
2.非结构化业务过程分解与群体路径规划方法。本文以结构化业务过程为研究对象,而非结构化业务过程分解与群体路径规划问题还需要在本文基础上做进一步的研究,下一步的工作将包括对非结构化业务过程并行分解算法的改进和群体规划体系结构的扩展等。
Migrating workflow is a workflow management paradigm based on mobile agent technology. In a migrating workflow system, a migrating instance(MI) acts as the task executer. It catches the task list and data with an execution objective, migrates from one workplace to another, utilizes the service provided by the workplaces and accepts the service results, without needing to exchange data with the workflow management engine. By this way, the control flow that concentrated in the center engine can be decentralized to the migrating instances. During the execution period, a migrating instance will determine its routing path according to the dynamic execution environment. When the migrating instance finds that the current workplace can not meet its requirements to execute the task, it will migrate to another available workplace and go on. Except for migrating time, the migrating instance does not depend on the reliability of network connection. Therefore, migrating workflow model greatly improves the adaptability to the dynamic execution environment. Especially, the model adapts to those concurrent processes of distributed business that need large number of remote procedure call (RPC) in a changeful execution environment.
The essence of migrating workflow model is to utilize the swarm intelligence of migrating instances to achieve the overall workflow execution goal. The key issue is the migrating instance path planning, which is to assign the tasks to the migrating instances and plan the optimal actions according to the specific execution environment so as to achieve the execution objective. According to the planning idea of AI, the path planning of migrating instances mainly consists of three key issues: process partition, individual path planning and group planning with multi migrating instance cooperation. The purpose of process partition is to separate a workflow process into a set of sub-processes, each sub-process with a sequence of tasks and an expected goal will be assigned to a migrating instance. Based on the results of process partition, the individual path planning is to select a most suitable workplace sequence for the sub-process so as to reach its individual goal in a dynamic and uncertain environment. Based on the individual planning, the group planning will take into account the group cooperation among the migrating instances for the workflow global goal, which includes the organizational structure of migrating instances, communication protocols and conflict resolution strategies.
Supported by the National Natural Science Foundation of China "Research on the methods of goal-oriented migrating workflow", this thesis focuses on two issues: process partition and path planning based on the migrating workflow system framework proposed by the Mobile Computing Laboratory of Shandong University, which includes:process fragmentation based on the domain-cover sub-tree, process parallel partition method with a master-slave structure, static task planning for sub-processes, migrating instance individual planning with uncertain environment, and partial global planning. The study has been proved and analyzed on a prototype migrating workflow platform.
The main contributions of this work are described as follows.
1. Research on workflow process partition method for multi-leveled master-slave cooperation of the migrating instances.
Different from the RPC based workflow process fragmentation methods, the objective of process partition in a migrating workflow is to cater for the migrating instance group planning. Since the relations among the migrating instances are based on the relations between the sub-processes they catch, the collaboration relations among the migrating instances have been taken into account before partitioning. The process partition in this work consists of two steps, which are domain fragmentation and parallel partition. The former aims at large workflow process, with the purpose of reducing the high complexity of parallel partition and migrating instance group cooperation. This thesis proposes a maximum sub-tree based method which fragments a workflow process into a set of domain-processes. Each domain-process with a relative independent domain attribute will be parallel partitioned in the next step. The parallel partition is to divide a process or a domain-process into a set of task-sequences with master-slave relations among them. The main idea of parallel partition is that, repeatedly search for the critical path of DAG (or sub-DAGs) of the process, and then separate the obtained critical path from the DAG and the remained sub-DAGs until the process has been completely partitioned. The master-slave relations among the sub-processes generated by the parallel partition will become the relations among migrating instances. In order to meet the quality of service (QoS) constrain, this thesis studies not only the structure partition but also the QoS allocation methods, and presents a discrete particle swarm optimization algorithm for sub-process static path planning.
2. Research on migrating instance individual path planning in uncertain execution environments.
Since the execution environment is changeful and uncertain, it is hard for a migrating instance to make a long term planning. A feasible way is to take a periodic optimizing planning according to the specific environment. This thesis models the individual path planning problem with Markov decision process (MDP), which segments the stages by tasks and define the execution state variables as remain deadline, time offset and planning step length. In each stage, the migrating instance determines a planning window according to dynamic environment and searches for the optimal routing path which meets the QoS constraints. Since the planning step length depends on the uncertainty of execution environment, it is possible to give a measurement method for the uncertainty of execution environment. Thus we reference the concept of entropy and present an approach to calculate the stability entropy of a workplace by periodic sampling the change of the quality of service and quantity of service. Based on the stability entropy of the available workplaces, the uncertainty of the execution environment can be measured, which enable the migrating instance to set the planning step length in each stage. The experiment results prove that the proposed approach achieves the satisfactory trade-off between the adaptability to the environment and execution performance.
3. Research on partial global path planning for migrating instance group cooperation.
The objective of migrating instance individual path planning is to optimize its execution performance without considering the execution of its partners'. However, due to lack of the group cooperation, the migrating instance plans its routing path based only on the observations about environment by itself and care only about the objective of its own. So the planning strategy can be optimal for the migrating instance itself, but not for the global workflow. This thesis models the migrating instances group planning as a partially observable Markov decision process (POMDP), and proposes a partial global planning architecture that divides the group planning problem into two layers:cooperation layer and individual planning layer. The cooperation layer focuses on group cooperation, which includes the organization structure of migrating instances, conflict resolution principle and communication protocols. The goal of cooperation layer is to determine the individual planning objective for each task frame and does not have to handle the details of task planning. The individual planning layer focuses on the implementation of the objective obtained by the cooperation layer and does not have to care about the group cooperation. For the cooperation layer, we propose an MI cooperative organization based on tree structure. Based on this structure, we also put forward a set of communication protocols between the MIs, as well as the resolution principles and methods of service conflicts and objective conflicts. The two-layer partial global planning architecture provides a way to simplify the complexity of group planning problem, which offers a valuable resolution of multi-agent collaborative computing in the workflow management applications.
The main innovative contributions of this thesis are summarized as follows.
1. This thesis proposes a process parallel partition method with a multi-leveled master-slave structure.
Different from the process partition methods in a centralized workflow with WfMC model, the objective of process partition in a migrating workflow is to support the orderly cooperation among the migrating instances. The parallel partition method proposed in this thesis fragments a process into a set of task-sequences, in which the synchronization tasks are served as the cooperation ports. The master-slave relations among the task-sequences are expressed as a partition tree which can be equivalently mapped into an organization tree of migrating instances after task assignment. Based on the master-slave relations and cooperation ports, the migrating instances can achieve on-demand consultation and orderly cooperation. Compared with the partition approaches without master-slave relations, the partition tree makes the cooperation relations more clearly and thus can support the autonomous cooperation of migrating instances.
2. This thesis presents online path planning method for migrating instances based on MDP and uncertain execution environments.
Different from the path planning approaches with global execution environments, the key idea of the online path planning method proposed in this thesis is to measure the uncertainty of the execution environment and take actions according to this measurement. Referencing the concept of entropy, this thesis presents an approach to measure the uncertainty of the execution environment and enable a migrating instance to make actions within a planning window that is set based on the execution environment. So compared with the one-step greedy planning strategies, our method can find a way to achieve the satisfactory trade-off between the adaptability to the execution environment and the overall execution performance of the migrating workflow.
3. This thesis proposes a POMDP based method for migrating instances partial global path planning and puts forward a group planning architecture.
In addition to the process partition method that must support the group cooperation of migrating instances, the other objective of group planning is to improve the execution efficiency of the workflow process. The partial global path planning method proposed in this thesis is modeled based on POMDP, which segments the global planning stages by the synchronization tasks and makes the individual planning within a task frame. Task frames are generated by dividing a task-sequence with synchronization tasks. The group planning assigns the workflow overall goal to the migrating instances and the individual planning focuses on the implementation of the partial goal obtained in the group planning. Compared with non-layered group planning methods, the architecture with cooperation layer and individual planning layer can effectively reduce the complexity of migrating instances group planning and improve the flexibility of individual planning methods.
The migrating workflow process partition and planning methods proposed in this thesis have been testified in simulation experiments and application cases. However, the migrating instances group planning is a complex problem, so there are still many aspects to be improved. To further the research started in this thesis, we propose the following future works:
1. Methods to online process partition and task clustering. In a complex and changeful environment, a workflow process depends only on the pre-partitioning before execution, the adaptability of the partition granularity is insufficient. So the study of online process partitioning and task clustering will be practically useful. In the future work, we suggest adopting the process partition into the migrating instance online path planning so that a process can be dynamically partitioned on-demand.
2. Process partition and planning methods for unstructured workflows. This work is based on structured workflow, so there are still research aspects to be further studied in unstructured workflows, such as unstructured process parallel partition and group path planning. We should further improve on the process partition algorithm and the architecture of migrating instances group planning.
引文
[1]Workflow Management Coalition. WFMC Workflow Management Coalition Terminology and Glossary. Brussels:Technical Report, WfMC-TC-1011, 1996.
[2]范玉顺.工作流管理技术基础一实现企业业务过程重组、过程管理与业务过程自动化的核心技术.北京:清华大学出版社.2001.
[3]史美林等WfMS:工作流管理系统.计算机学报,1999,Vol.22(3)：325-334.
[4]Edward A. Stohr, J. Loan Zhao. Workflow Automation:Overview and Research Issues. Information Systems Frontiers.2001, Vol.3(13):281-296.
[5]Glatard T,Montagnat J,Lingrand D,et al. Flexible and Efficient Workflow Deployment of Data-Intensive Applications on Grids with MOTEUR. International Journal of High Performance Computing Applications.2008, Vol.22(3):347-360.
[6]Ewa D, Dennis G, Matthew S, Ian T. Workflows and e-Science:An overview of workflow system features and capabilities Future Generation Computer Systems.2009, Vol.25(5):528-540.
[7]Workflow Management Coalition:Workflow Management Coalition Terminology and Glossary (WFMC-TC-1011 Issue 3.0).1999.
[8]Gustavo Alonso, Hans-Jorg Schek. Research Issues in Large Workflow Management System. Proceedings of NSF Workshop on Workflow and Process Automation in Information Science.1996:126-132.
[9]Nikitas A. Assimakopoulos, Apostolos E. Lydakis. The Use of Systemic methodologies in workflow management. Proceedings of the 47th Annual Meeting of the International Society for the Systems Sciences, at Hersonissos, Crete,2003. [Online]. http://www.systemicbusiness.org/digests/sabi2003/2003_ISSS_47th_067_Assimakopoulos_Lydakis.pdf.
[10]Budimac Z, Pesovic D, Ivanovic M, et al. Lessons learned from the implementation of a workflow management system using mobile agents. Novi Sad Journal of Mathematics.2006,36(2):65-79.
[11]Cai T, Gloor P, Nog S. Dartflow:a workflow management system on the web using transportable agents. Dept. of Computer Science, Dartmouth College, Hanover,1996.
[12]Fakas G, Karakostas B. A workflow management system based on intelligent collaborative objects. Information and Software Technology.1999,41(13): 907-915.
[13]Yoo J-J, Lee D, Suh Y-H, et al. Scalable workflow system model based on mobile agents. In:Yuan S-T, Yokoo M (eds) Intelligent agents:specification, modeling, and application. Lecture notes in computer science. Springer, Berlin, 2001, Vol.2132:222-236.
[14]Valetto G, Kaiser G, Kc GS. A mobile agent approach to process-based dynamic adaptation of complex software systems. Lecture notes in computer science. Springer, Berlin,2001:102-116.
[15]Verginadis Y, Mentzas G. agents and workflow engines for inter-organizational workflows in e-government cases. Business Process Management Journal.2008,Vol.14(2):188-203.
[16]李红臣,史美林agent在工作流管理系统中的应用研究.通信学报.1999,20(9)：16-22.
[17]吴刚,吴泉源,王怀民.一种基于移动智能体的工作流管理模型.计算机辅助设计与图形学学报.2001,Vol.13(6)：527-531.
[18]Robert S G, George C, David K, et al. Daniela RusD'Agents:Applications and performance of a mobile-agent system. Software:Practice and Experience. 2002,Vol.32(6):543-573.
[19]Bellavista P,Corradi, A, Stefanelli C.Mobile Agent Middleware for Mobile Computing.Computer.2001,Vol.34(3):73-81.
[20]Cichocki A, Rusinkiewicz M. Migrating workflows. Workflow Management Systems and Interoperability.1998,Vol.164:339-355.
[21]Cichocki A., Rusinkiewicz M., Providing transactional properties for migrating workflows. Mobile Networks and Applications.2004,9(5):473-480.
[22]曾广周,党妍.基于移动计算范型的迁移工作流研究计算机学报.2003,Vol.26(10)：1343-1349.
[23]Franco Z, Nicholas R J, Michael W.Organisational Abstractions for the Analysis and Design of Multi-Agent Systems. International Workshop on Agent-Oriented Software Engineering.2000.127-141.
[24]林闯.随机Petri网和系统性能评价.北京清华大学出版社,2000.
[25]Ammar H H,Islam S M R. Timed scale decomposition of a class of generalized stochastic Petn models. IEEE Transaction on Software Engineering.1989, Vol.15(6):809-820.
[26]顾元勋.基于单元关系度技术的Petri网模型分解,系统工程学报,2003,Vol.18(6)：491-497
[27]曾庆田,吴哲辉.基于分解的结构复杂Petri网的语言行为描述.系统工程学报.2006,Vol.19(3)：301-306.
[28]王培良.Petri网的并分解.控制理论与应用,2001,Vol.18(1)：117-118.
[29]胡红革,谢阅,黄大贵,基于位置不变量的Petri网分解方法.2004,Vol.18(12)：77-80.
[30]Duan R, Prodan R, Fahringer T. Run-time Optimization for Grid Workflow Applications.7th IEEE/ACM International Conference on Grid Computing.2006:33-40.
[31]许可,吴澄.网格服务流的状态π演算形式化验证技术研究与应用.清华大学工学博士学位论文.2007.
[32]Tan W, Fan Y. Model fragmentation for distributed workflow execution:a Petri net approach. Lecture Notes in Computer Science. Springer-Verlag,2005: Vol.3563:207-214.
[33]Tan W, Fan Y. Dynamic workflow model fragmentation for distributed execution. Computers in Industry.2007, Vol.58 (5):381-391.
[34]孙红俊,范玉顺.面向服务的分布式工作流执行站点优化.计算机集成制造系统.2009,Vol.15(7),1398-1405.
[35]Nanda M G, Chandra S, Sarkar V. Decentralizing execution of composite Web services, Proceedings of the 19th annual ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications. 2004:170-187.
[36]Nanda M G, Karnik N. Synchronization analysis for decentralizing composite Web services. Proceedings of ACM Symposium on Applied Computing.2003: 407-414.
[37]Baresi L, Maurino A, Modafferi S. Partitioning of workflows on mobile information systems. Proceedings of the IFIP TC8 working conference on mobile information systems (MOBIS).2004:93-106.
[38]Maurino, A., Modafferi, S., Partitioning rules for orchestrating mobile information systems. Personal and Ubiquitous Computing.2005,9(5). 291-300.
[39]康小强.多agent系统中的agent模型与合作策略研究.清华大学博士学位论文.1999.
[40]Edmund Durfee, Victor R. Lesser. Partial global planning:a coordination framework for distributed hypothesis formation. IEEE Transactions on Systems, Man, and Cybernetics.1991:1167-1183.
[41]史忠植.高级人工智能(第二版).悲哀京：科学出版社.2006.
[42]刘必欣,王玉峰,贾焰,吴泉源.一种基于角色的分布式动态服务组合方法.软件学报.2005,Vol.16(11)：1859-1867.
[43]Deelman E. Grids and Clouds:Making Workflow Applications Work in Heterogeneous Distributed Environments. International Journal of High Performance Computing Applications.2010, Vol.24(3):284-298.
[44]Singh G, Su M H, Vahi K, et al. Workflow Task Clustering for Best Effort Systems with Pegasus, Proceedings of the 15th ACM Mardi Gras conference. 2008.[Online] http://pegasus.isi.edu/publications/.
[45]谢国琪.基于带权与或树和AOE-网的多智能体动态任务规划研究.中南大学硕士学位论文.2010.
[46]刘波,罗军舟,李伟.大规模网络管理中的任务分解与调度.通信学报.2006,Vol.3：64-72.
[47]Feng Y, Cai W. Cao, J. Dynamic partner identification in mobile agent-based distributed job workflow execution. Journal of Parallel Distributed Computing. 2007, Vol.67:1137-1154.
[48]Ferrante J, Ottenstein K J, Warren J D. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems,1987, Vol.9(3):319-349.
[49]Morel B, Alexander P A. slicing approach for parallel component adaptation.10th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems.2003.108-114.
[50]Zhuang X, Pande S. Compiler scheduling of mobile agents for minimizing overheads. Proceedings of the 23th International Conference on Distributed Computing Systems.2003.600-609.
[51]Pinar S, Ismail H. Toroslu. An architecture for workflow scheduling under resource allocation constraints. Information Systems.2005,Vol.30(5):399-422.
[52]Yu J, Buyya R. Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms. Scientific Programming.2006, Vol.14(3):217-230.
[53]Michael Z M. Resource Modeling in Workflow Applications. Proceedings of the 1999 Workflow Management Conference.1999:137-153.
[54]Jin H S, Seok K O, Kyung H C, et al. An Efficient Workflow Task Allocation Method in A Distributed Execution Environment. Journal of Systems and Software.2003,Vol.67(3):165-179.
[55]李鲁艳,曾广周.基于任务片的旅行图生成算法研究.计算机工程与应用.2008,44(32)：41-46.
[56]陈廷伟,张斌,郝宪文.基于任务-资源分配图优化选取的网格依赖任务调度.计算机研究与发展.2007,Vol.44(10)：1741-1750.
[57]吴强,边计年,薛宏熙.系统级综合中结合资源分配的调度算法.软件学报.2007,Vol.18(2)：220-228.
[58]Erol K, Hendler J, Nau D. HTN planning:complexity and expressivity. Proceedings of the Twelfth National conference on Artificial Intelligence. 1994:1123-1128.
[59]Beaumont O, Casanova H, Legrand A. Scheduling divisible loads on star and tree networks:results and open problems. IEEE Trans on Parallel and Distributed Systems,2005, Vol.16(3):207-218.
[60]Veeravalli B, Yao J. Divisible load scheduling strategies on distributed multi-level tree networks with communication delays and buffer constraints. Computer Communications,2004, Vol.27(1):93-110.
[61]罗杰文,史忠植.基于动态描述逻辑的多主体协作模型.计算机研究与发展,2006,Vol.43(8)：1317-1322.
[62]王汝传,徐小龙.智能体agent及其在信息网络中的应用.北京：北京邮电出版社.2006.
[63]Darius B, Craig B. S. Local Search for POMDP Controllers. In The Nineteenth National Conference on Artificial Intelligence.2004:690-696.
[64]Pascal P. Exploiting Structure to Efficiently Solve Large Scale Partially Observable Markov Decision Processes. PhD thesis, University of Toronto, 2005.
[65]Smith T, Simmons R. Heuristic Search Value Iteration for POMDPs. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence. 2004. [Online]http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.2382 & rep=rep1&type=.pdf.
[66]M. T. J. Spaan and N. Vlassis. A Point-Based POMDP Algorithm for Robot Planning. In Proceedings of the IEEE International Conference on Robotics and Automation,2004:2399-2404.
[67]Bharaneedharan Rathnasabapathy, Piotr Gmytrasiewicz. Formalizing Multi-agent POMDP's in the context of network routing. Proceedings of the 36th Hawaii International Conference on System Sciences.2003. [Online] http://citeseerx,sit.psu.edu/viewdoc/cownload?doi=10.1.1.10.6821&rep=rep1& type=pdf.
[68]李响,陈小平.一种适应动态不确定环境的规划系统POMDPRS的形式描述.小型微型计算机系统.2009,Vol.30(7)：1274-1281.
[69]Poupart P. Exploiting structure to efficiently solve large scale partially observable Markov decision processes. University of Toronto.2005.[Online] www.cs.uwaterloo.ca/-ppoupart/publications/ut-thesis/ut-thesis.ps.
[70]Sebastien P, Ludovic T, Brahim C. An online POMDP algorithm for complex multi-agent environment. Proceedings of The fourth International Joint Conference on Autonomous agents and Multi agent Systems (AAMAS-05). 2005:970-977.
[71]Zhang N L, Liu W J. Planning in stochastic domains:Problem characteristics and approximation. Technical Report HKUST-CS96-31.1996. [Online] citeseerx. ist.psu. edu/viewdoc/download?doi=10.1.1.29.9704&rep=rep1&type=pdf.
[72]David V P, Milind T. The communicative multi-agent team decision problem: Analyzing teamwork theories and models. Journal of Artificial Intelligence Research.2002,Vol.16:389-423.
[73]Cassandra A, Littman M L, Zhang N L, et al. Increment al pruning:A simple, fast, exact method for partially observable markov decision process. Proceedings of the 13th Annual Conference on Uncertainty in Artificial Intelligence.1997:54-61.
[74]Paquet S, Tobin L, Chaibdraa B. An Online POMDP Algorithm for Complex Multi-agent Environments. Proceedings of the fourth International Joint Conference on Autonomous agents and Multi agent Systems.2005:970-977.
[75]仵博,吴敏.一种基于信念状态压缩的实时POMDP算法.控制与决策.2007,Vol.22(12)：1418-1421.
[76]陈茂,陈小平.基于采样的POMDP近似算法计算机仿真.2006,V01.23(5)：64-67.
[77]Damien P. Distributed planning through graph merging. Proceedings International Conference on agents and Artificial Intelligence.2010:129-134.
[78]Brammert O, Boi F. Coordinating agent Plans through Distributed Constraint Optimization. Proceedings of 18th International Workshop on Multiagent Planning and Scheduling.2008.[Online] masplan.isr.ist.utl.pt/papers/Ottens. pdf.
[79]Yoonheui K, Ranjit r, Pradeep V, et al. Exploiting locality of interaction in networked distributed POMDPs. In AAAI Spring Symposium on Distributed Planning and Scheduling.2006. [Online] citeseerx.ist.psu.edu/ viewdoc/download?Doi=10.1.1.139.7351&rep= rep1 & type=pdf.
[80]Robert P G, David J M, Edmund H D. Coordinating Highly Contingent Plans: Biasing Distributed MDPs Towards Cooperative Behavior. Proceeding of 15th International Workshop on Multi-agent Planning and Scheduling.2009. [Online] citeseerx. ist. psu. edu/vi ewdoc/download? doi=10.1.1.14.2123&rep=rep 1&type=pdf.
[81]Chades L, Shcerrer B, Charpillet F. A heuristic approach for solving decentralized-POMDP:as sessment on the pursuit problem. Proceedings of the 2002 ACM Symposiumon Applied Computing.2002.57-62.
[82]张新良,石纯一M-POMDP模型及其划分求解算法.清华大学学报(自然科学版).2005,Vol.45(10)：1413-1416.
[83]Loke S, Zaslavsky A. Towards distributed workflow enactment with itineraries and mobile agent management. Proceedings of the Ecommerce agents 2001:283-294.
[84]Foster S, Moore D, Nebesh B. Flester, et al. Control and management in a mobile agent workflow architecture. Proceedings of the Third International Conference on Autonomous agents. [Online] dwarfworks.com/ceallach/ autopilot.doc.
[85]Merz M, Liberman B, Lamersdorf W. Using mobile agents to support inter organizational workflow management. Applied Artificial Intelligence.1997, Vol.11(6),551-572.
[86]Meng J, Helal S, Su S. An ad-hoc workflow system architecture based on mobile agents and rule-based processing, Proceedings of the International Conference on Artificial Intelligence.2000. [Online] www.icta.ufl.edu/projects/publications/adhocWF.pdf.
[87]范志强.基于组件的轻量级迁移实例创建研究山东大学硕士学位论文.2006.
[88]任明,王成道.基于联邦结构的多agent协作.华东理工大学学报.2004,V01.30(3)：311-314.
[89]张晓光,曹健,张申生等.面向工作流结构优化的扩展关键路径分析.上海交通大学学报.2004,Vol.38(1)：29-33.
[90]Brafman R I. A heuristic variable grid solutions method for POMDPs. Proceedings of the 14th National Conference on Artificial Intelligence, 1997:727-733.
[91]方晨,王凌.资源约束项目调度研究综述控制与决策.2010.Vol.25(5)：641-650
[92]Cheng J, Zeng G Z. Task Decomposition and Planning in Resource-constrained Workflow. Fifth International Conference on Natural Computation. 2009:218-323.
[93]Pan Q, Tasgetiren M F, Liang Y C. A Discrete Particle Swarm Optimization Algorithm for Single Machine Total Earliness and Tardiness Problem with a Common Due Date, IEEE Congress on Evolutionary Computation:2006, 3281-3288.
[94]Honig U, Schiffmann W. A Comprehensive test bench for the evaluation of scheduling heuristics. International Association of Science and Technology for Development.2005,Vol.16:437-442.
[95]Wu X, Zeng G. Goals description and application in migrating workflow system. Expert Systems with Applications.2010, Vol.37(12):8027-8035.
[96]Yu J. QoS-based Scheduling of Workflows on Global Grids.Thesis for Doctor's Degree, The University of Melbourne, Australia,2007.
[97]王睿.面向目标的迁移工作流主动服务方法研究.山东大学博士学位论文.2009.
[98]朱晓健.基于信息熵的博弈支付及纳什均衡选择研究.大连理工大学硕士学位论文.2008.
[99]Shannon C E. A Mathematical Theory of Communication. Bell System Technical Journal.1948,Vol.21:379-423.
[100]何径舟,王厚峰.基于特征选择和最大熵模型的汉语词义消歧.软件学报.Vol.21(6)：1287-1295.
[101]Xing Y. SRCB-WSD:Supervised Chinese word sense disambiguation with key features. Proceedings of the 4th Int'l Workshop on Semantic Evaluations. 2007.300-303.
[102]林亚平,刘云中,周顺先等.基于最大熵的隐马尔可夫模型文本信息抽取.电子学报.2005,Vol.33(2)：237-241.
[103]应伟勤,李元香,SHEU Phillip C-Y等.演化多目标优化中的几何热力学选择.计算机学报.2010,Vol.33(4)：755-767.
[104]卢致杰,覃正.基于信息网格的智能多代理系统QoS优化研究.计算机工程.2005,V01.31(15)：13-15.
[105]王嫚,徐惠民.基于熵的网格资源QoS优化策略.北京邮电大学学报.2006,V01.29(4)：30-33.
[106]雷博,范九伦.广义模糊熵阈值法中基于粒子群优化的参数选取.控制与决策.2009,Vol.24(3)：446-450.
[107]朱学军,陈彤,薛量,李峻.多个体参与交叉的Pareto多目标遗传算法.电子学报.2001,Vol.29(1)：106-109.
[108]史忠植.高级人工智能(第二版).北京：科学出版社.2006.
[109]Sonmk E J. The Optimal control of partially observable Markov processes over the infinite horizon:Discounted costs. Operations Research,1978, Vol.26(2): 282-304.
[110]Kaelbling L P,Littman M L, Cassandra A R. Planning and acting in partially observable stochastic domains. Artificial Intelligence.1998,101:99-134.
[111]张波,蔡庆生 口语对话系统的POMDP模型及求解.计算机研究与发展,2002,Vol.39(2)：217-224.
[112]Cheng H T. Algorithms for partially observable Markov decision processes. Thesis for Doctor's Degree. Vancouver Columbia:University of British Columbia,1998.
[113]Zhang N L, Zhang W. Speeding up the convergence of value iteration in partially observable Markov decision processes. Journal of Artificial Intelligence Research.2001,Vol.14:29-51.
[114]Cassandra A, Littaman M, Zhang N. Incremental pruning:A simple, fast, exact method for partially observable Markov decision processes. Proceedings of the 13th Annual Conf. on Uncertainty in Artificial Intelligence.1997:54-61.
[115]周继恩,刘贵全.基于内部信念状态POMDP模型在用户兴趣获取中的应用.小型微型计算机系统.2004,Vol.25(11)：1979-1983.
[116]Poupart P. Exploiting structure to efficiently solve large scale partially observable Markov decision processes. Toronto:University of Toronto. 2005.[Online] ww.cs.uwaterloo.ca/-ppoupart/publications/ut-thesis/ut-thesis.ps.
[117]Daniel S Bernstein, Eric A Hansen, Shlomo Zilberstein. Bounded policy iteration for decentralized POMDPs. Edinburgh, Scotland:The Proceedings of the 19th International Joint Conference on Artificial Intelligence. 2005:1287-1292.
[118]Dima B, Michel D R, Anatol S. On the complexity of partially observed Markov decision processes. Theoretical Computer Science,1996, Vol.157(2): 161-183.
[119]Papadimitriou C H, Tsitsiklis J N. The complexity of Markov decision processes. Mathematics of Operations Research.1987,Vol.12(3):441-450.
[120]Littrnan M L, Cassandra A, Kaelbling L. Learning policies for partially observable environments:Scaling up. Proceedings of the Twelfth International Conference on Machine Learning. San Francisco, CA:Morgan Kaufmann Publishers,1995:362-370.
[121]Pineau J, Gordon G Thrun S. Point-based value iteration:an anytime algorithm for POMDPs. Proceedings of International Joint Conference on Artificial Intelligence.2003:1025-1032.
[2]范玉顺.工作流管理技术基础一实现企业业务过程重组、过程管理与业务过程自动化的核心技术.北京:清华大学出版社.2001.
[3]史美林等WfMS:工作流管理系统.计算机学报,1999,Vol.22(3)：325-334.
[4]Edward A. Stohr, J. Loan Zhao. Workflow Automation:Overview and Research Issues. Information Systems Frontiers.2001, Vol.3(13):281-296.
[5]Glatard T,Montagnat J,Lingrand D,et al. Flexible and Efficient Workflow Deployment of Data-Intensive Applications on Grids with MOTEUR. International Journal of High Performance Computing Applications.2008, Vol.22(3):347-360.
[6]Ewa D, Dennis G, Matthew S, Ian T. Workflows and e-Science:An overview of workflow system features and capabilities Future Generation Computer Systems.2009, Vol.25(5):528-540.
[7]Workflow Management Coalition:Workflow Management Coalition Terminology and Glossary (WFMC-TC-1011 Issue 3.0).1999.
[8]Gustavo Alonso, Hans-Jorg Schek. Research Issues in Large Workflow Management System. Proceedings of NSF Workshop on Workflow and Process Automation in Information Science.1996:126-132.
[9]Nikitas A. Assimakopoulos, Apostolos E. Lydakis. The Use of Systemic methodologies in workflow management. Proceedings of the 47th Annual Meeting of the International Society for the Systems Sciences, at Hersonissos, Crete,2003. [Online]. http://www.systemicbusiness.org/digests/sabi2003/2003_ISSS_47th_067_Assimakopoulos_Lydakis.pdf.
[10]Budimac Z, Pesovic D, Ivanovic M, et al. Lessons learned from the implementation of a workflow management system using mobile agents. Novi Sad Journal of Mathematics.2006,36(2):65-79.
[11]Cai T, Gloor P, Nog S. Dartflow:a workflow management system on the web using transportable agents. Dept. of Computer Science, Dartmouth College, Hanover,1996.
[12]Fakas G, Karakostas B. A workflow management system based on intelligent collaborative objects. Information and Software Technology.1999,41(13): 907-915.
[13]Yoo J-J, Lee D, Suh Y-H, et al. Scalable workflow system model based on mobile agents. In:Yuan S-T, Yokoo M (eds) Intelligent agents:specification, modeling, and application. Lecture notes in computer science. Springer, Berlin, 2001, Vol.2132:222-236.
[14]Valetto G, Kaiser G, Kc GS. A mobile agent approach to process-based dynamic adaptation of complex software systems. Lecture notes in computer science. Springer, Berlin,2001:102-116.
[15]Verginadis Y, Mentzas G. agents and workflow engines for inter-organizational workflows in e-government cases. Business Process Management Journal.2008,Vol.14(2):188-203.
[16]李红臣,史美林agent在工作流管理系统中的应用研究.通信学报.1999,20(9)：16-22.
[17]吴刚,吴泉源,王怀民.一种基于移动智能体的工作流管理模型.计算机辅助设计与图形学学报.2001,Vol.13(6)：527-531.
[18]Robert S G, George C, David K, et al. Daniela RusD'Agents:Applications and performance of a mobile-agent system. Software:Practice and Experience. 2002,Vol.32(6):543-573.
[19]Bellavista P,Corradi, A, Stefanelli C.Mobile Agent Middleware for Mobile Computing.Computer.2001,Vol.34(3):73-81.
[20]Cichocki A, Rusinkiewicz M. Migrating workflows. Workflow Management Systems and Interoperability.1998,Vol.164:339-355.
[21]Cichocki A., Rusinkiewicz M., Providing transactional properties for migrating workflows. Mobile Networks and Applications.2004,9(5):473-480.
[22]曾广周,党妍.基于移动计算范型的迁移工作流研究计算机学报.2003,Vol.26(10)：1343-1349.
[23]Franco Z, Nicholas R J, Michael W.Organisational Abstractions for the Analysis and Design of Multi-Agent Systems. International Workshop on Agent-Oriented Software Engineering.2000.127-141.
[24]林闯.随机Petri网和系统性能评价.北京清华大学出版社,2000.
[25]Ammar H H,Islam S M R. Timed scale decomposition of a class of generalized stochastic Petn models. IEEE Transaction on Software Engineering.1989, Vol.15(6):809-820.
[26]顾元勋.基于单元关系度技术的Petri网模型分解,系统工程学报,2003,Vol.18(6)：491-497
[27]曾庆田,吴哲辉.基于分解的结构复杂Petri网的语言行为描述.系统工程学报.2006,Vol.19(3)：301-306.
[28]王培良.Petri网的并分解.控制理论与应用,2001,Vol.18(1)：117-118.
[29]胡红革,谢阅,黄大贵,基于位置不变量的Petri网分解方法.2004,Vol.18(12)：77-80.
[30]Duan R, Prodan R, Fahringer T. Run-time Optimization for Grid Workflow Applications.7th IEEE/ACM International Conference on Grid Computing.2006:33-40.
[31]许可,吴澄.网格服务流的状态π演算形式化验证技术研究与应用.清华大学工学博士学位论文.2007.
[32]Tan W, Fan Y. Model fragmentation for distributed workflow execution:a Petri net approach. Lecture Notes in Computer Science. Springer-Verlag,2005: Vol.3563:207-214.
[33]Tan W, Fan Y. Dynamic workflow model fragmentation for distributed execution. Computers in Industry.2007, Vol.58 (5):381-391.
[34]孙红俊,范玉顺.面向服务的分布式工作流执行站点优化.计算机集成制造系统.2009,Vol.15(7),1398-1405.
[35]Nanda M G, Chandra S, Sarkar V. Decentralizing execution of composite Web services, Proceedings of the 19th annual ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications. 2004:170-187.
[36]Nanda M G, Karnik N. Synchronization analysis for decentralizing composite Web services. Proceedings of ACM Symposium on Applied Computing.2003: 407-414.
[37]Baresi L, Maurino A, Modafferi S. Partitioning of workflows on mobile information systems. Proceedings of the IFIP TC8 working conference on mobile information systems (MOBIS).2004:93-106.
[38]Maurino, A., Modafferi, S., Partitioning rules for orchestrating mobile information systems. Personal and Ubiquitous Computing.2005,9(5). 291-300.
[39]康小强.多agent系统中的agent模型与合作策略研究.清华大学博士学位论文.1999.
[40]Edmund Durfee, Victor R. Lesser. Partial global planning:a coordination framework for distributed hypothesis formation. IEEE Transactions on Systems, Man, and Cybernetics.1991:1167-1183.
[41]史忠植.高级人工智能(第二版).悲哀京：科学出版社.2006.
[42]刘必欣,王玉峰,贾焰,吴泉源.一种基于角色的分布式动态服务组合方法.软件学报.2005,Vol.16(11)：1859-1867.
[43]Deelman E. Grids and Clouds:Making Workflow Applications Work in Heterogeneous Distributed Environments. International Journal of High Performance Computing Applications.2010, Vol.24(3):284-298.
[44]Singh G, Su M H, Vahi K, et al. Workflow Task Clustering for Best Effort Systems with Pegasus, Proceedings of the 15th ACM Mardi Gras conference. 2008.[Online] http://pegasus.isi.edu/publications/.
[45]谢国琪.基于带权与或树和AOE-网的多智能体动态任务规划研究.中南大学硕士学位论文.2010.
[46]刘波,罗军舟,李伟.大规模网络管理中的任务分解与调度.通信学报.2006,Vol.3：64-72.
[47]Feng Y, Cai W. Cao, J. Dynamic partner identification in mobile agent-based distributed job workflow execution. Journal of Parallel Distributed Computing. 2007, Vol.67:1137-1154.
[48]Ferrante J, Ottenstein K J, Warren J D. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems,1987, Vol.9(3):319-349.
[49]Morel B, Alexander P A. slicing approach for parallel component adaptation.10th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems.2003.108-114.
[50]Zhuang X, Pande S. Compiler scheduling of mobile agents for minimizing overheads. Proceedings of the 23th International Conference on Distributed Computing Systems.2003.600-609.
[51]Pinar S, Ismail H. Toroslu. An architecture for workflow scheduling under resource allocation constraints. Information Systems.2005,Vol.30(5):399-422.
[52]Yu J, Buyya R. Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms. Scientific Programming.2006, Vol.14(3):217-230.
[53]Michael Z M. Resource Modeling in Workflow Applications. Proceedings of the 1999 Workflow Management Conference.1999:137-153.
[54]Jin H S, Seok K O, Kyung H C, et al. An Efficient Workflow Task Allocation Method in A Distributed Execution Environment. Journal of Systems and Software.2003,Vol.67(3):165-179.
[55]李鲁艳,曾广周.基于任务片的旅行图生成算法研究.计算机工程与应用.2008,44(32)：41-46.
[56]陈廷伟,张斌,郝宪文.基于任务-资源分配图优化选取的网格依赖任务调度.计算机研究与发展.2007,Vol.44(10)：1741-1750.
[57]吴强,边计年,薛宏熙.系统级综合中结合资源分配的调度算法.软件学报.2007,Vol.18(2)：220-228.
[58]Erol K, Hendler J, Nau D. HTN planning:complexity and expressivity. Proceedings of the Twelfth National conference on Artificial Intelligence. 1994:1123-1128.
[59]Beaumont O, Casanova H, Legrand A. Scheduling divisible loads on star and tree networks:results and open problems. IEEE Trans on Parallel and Distributed Systems,2005, Vol.16(3):207-218.
[60]Veeravalli B, Yao J. Divisible load scheduling strategies on distributed multi-level tree networks with communication delays and buffer constraints. Computer Communications,2004, Vol.27(1):93-110.
[61]罗杰文,史忠植.基于动态描述逻辑的多主体协作模型.计算机研究与发展,2006,Vol.43(8)：1317-1322.
[62]王汝传,徐小龙.智能体agent及其在信息网络中的应用.北京：北京邮电出版社.2006.
[63]Darius B, Craig B. S. Local Search for POMDP Controllers. In The Nineteenth National Conference on Artificial Intelligence.2004:690-696.
[64]Pascal P. Exploiting Structure to Efficiently Solve Large Scale Partially Observable Markov Decision Processes. PhD thesis, University of Toronto, 2005.
[65]Smith T, Simmons R. Heuristic Search Value Iteration for POMDPs. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence. 2004. [Online]http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.2382 & rep=rep1&type=.pdf.
[66]M. T. J. Spaan and N. Vlassis. A Point-Based POMDP Algorithm for Robot Planning. In Proceedings of the IEEE International Conference on Robotics and Automation,2004:2399-2404.
[67]Bharaneedharan Rathnasabapathy, Piotr Gmytrasiewicz. Formalizing Multi-agent POMDP's in the context of network routing. Proceedings of the 36th Hawaii International Conference on System Sciences.2003. [Online] http://citeseerx,sit.psu.edu/viewdoc/cownload?doi=10.1.1.10.6821&rep=rep1& type=pdf.
[68]李响,陈小平.一种适应动态不确定环境的规划系统POMDPRS的形式描述.小型微型计算机系统.2009,Vol.30(7)：1274-1281.
[69]Poupart P. Exploiting structure to efficiently solve large scale partially observable Markov decision processes. University of Toronto.2005.[Online] www.cs.uwaterloo.ca/-ppoupart/publications/ut-thesis/ut-thesis.ps.
[70]Sebastien P, Ludovic T, Brahim C. An online POMDP algorithm for complex multi-agent environment. Proceedings of The fourth International Joint Conference on Autonomous agents and Multi agent Systems (AAMAS-05). 2005:970-977.
[71]Zhang N L, Liu W J. Planning in stochastic domains:Problem characteristics and approximation. Technical Report HKUST-CS96-31.1996. [Online] citeseerx. ist.psu. edu/viewdoc/download?doi=10.1.1.29.9704&rep=rep1&type=pdf.
[72]David V P, Milind T. The communicative multi-agent team decision problem: Analyzing teamwork theories and models. Journal of Artificial Intelligence Research.2002,Vol.16:389-423.
[73]Cassandra A, Littman M L, Zhang N L, et al. Increment al pruning:A simple, fast, exact method for partially observable markov decision process. Proceedings of the 13th Annual Conference on Uncertainty in Artificial Intelligence.1997:54-61.
[74]Paquet S, Tobin L, Chaibdraa B. An Online POMDP Algorithm for Complex Multi-agent Environments. Proceedings of the fourth International Joint Conference on Autonomous agents and Multi agent Systems.2005:970-977.
[75]仵博,吴敏.一种基于信念状态压缩的实时POMDP算法.控制与决策.2007,Vol.22(12)：1418-1421.
[76]陈茂,陈小平.基于采样的POMDP近似算法计算机仿真.2006,V01.23(5)：64-67.
[77]Damien P. Distributed planning through graph merging. Proceedings International Conference on agents and Artificial Intelligence.2010:129-134.
[78]Brammert O, Boi F. Coordinating agent Plans through Distributed Constraint Optimization. Proceedings of 18th International Workshop on Multiagent Planning and Scheduling.2008.[Online] masplan.isr.ist.utl.pt/papers/Ottens. pdf.
[79]Yoonheui K, Ranjit r, Pradeep V, et al. Exploiting locality of interaction in networked distributed POMDPs. In AAAI Spring Symposium on Distributed Planning and Scheduling.2006. [Online] citeseerx.ist.psu.edu/ viewdoc/download?Doi=10.1.1.139.7351&rep= rep1 & type=pdf.
[80]Robert P G, David J M, Edmund H D. Coordinating Highly Contingent Plans: Biasing Distributed MDPs Towards Cooperative Behavior. Proceeding of 15th International Workshop on Multi-agent Planning and Scheduling.2009. [Online] citeseerx. ist. psu. edu/vi ewdoc/download? doi=10.1.1.14.2123&rep=rep 1&type=pdf.
[81]Chades L, Shcerrer B, Charpillet F. A heuristic approach for solving decentralized-POMDP:as sessment on the pursuit problem. Proceedings of the 2002 ACM Symposiumon Applied Computing.2002.57-62.
[82]张新良,石纯一M-POMDP模型及其划分求解算法.清华大学学报(自然科学版).2005,Vol.45(10)：1413-1416.
[83]Loke S, Zaslavsky A. Towards distributed workflow enactment with itineraries and mobile agent management. Proceedings of the Ecommerce agents 2001:283-294.
[84]Foster S, Moore D, Nebesh B. Flester, et al. Control and management in a mobile agent workflow architecture. Proceedings of the Third International Conference on Autonomous agents. [Online] dwarfworks.com/ceallach/ autopilot.doc.
[85]Merz M, Liberman B, Lamersdorf W. Using mobile agents to support inter organizational workflow management. Applied Artificial Intelligence.1997, Vol.11(6),551-572.
[86]Meng J, Helal S, Su S. An ad-hoc workflow system architecture based on mobile agents and rule-based processing, Proceedings of the International Conference on Artificial Intelligence.2000. [Online] www.icta.ufl.edu/projects/publications/adhocWF.pdf.
[87]范志强.基于组件的轻量级迁移实例创建研究山东大学硕士学位论文.2006.
[88]任明,王成道.基于联邦结构的多agent协作.华东理工大学学报.2004,V01.30(3)：311-314.
[89]张晓光,曹健,张申生等.面向工作流结构优化的扩展关键路径分析.上海交通大学学报.2004,Vol.38(1)：29-33.
[90]Brafman R I. A heuristic variable grid solutions method for POMDPs. Proceedings of the 14th National Conference on Artificial Intelligence, 1997:727-733.
[91]方晨,王凌.资源约束项目调度研究综述控制与决策.2010.Vol.25(5)：641-650
[92]Cheng J, Zeng G Z. Task Decomposition and Planning in Resource-constrained Workflow. Fifth International Conference on Natural Computation. 2009:218-323.
[93]Pan Q, Tasgetiren M F, Liang Y C. A Discrete Particle Swarm Optimization Algorithm for Single Machine Total Earliness and Tardiness Problem with a Common Due Date, IEEE Congress on Evolutionary Computation:2006, 3281-3288.
[94]Honig U, Schiffmann W. A Comprehensive test bench for the evaluation of scheduling heuristics. International Association of Science and Technology for Development.2005,Vol.16:437-442.
[95]Wu X, Zeng G. Goals description and application in migrating workflow system. Expert Systems with Applications.2010, Vol.37(12):8027-8035.
[96]Yu J. QoS-based Scheduling of Workflows on Global Grids.Thesis for Doctor's Degree, The University of Melbourne, Australia,2007.
[97]王睿.面向目标的迁移工作流主动服务方法研究.山东大学博士学位论文.2009.
[98]朱晓健.基于信息熵的博弈支付及纳什均衡选择研究.大连理工大学硕士学位论文.2008.
[99]Shannon C E. A Mathematical Theory of Communication. Bell System Technical Journal.1948,Vol.21:379-423.
[100]何径舟,王厚峰.基于特征选择和最大熵模型的汉语词义消歧.软件学报.Vol.21(6)：1287-1295.
[101]Xing Y. SRCB-WSD:Supervised Chinese word sense disambiguation with key features. Proceedings of the 4th Int'l Workshop on Semantic Evaluations. 2007.300-303.
[102]林亚平,刘云中,周顺先等.基于最大熵的隐马尔可夫模型文本信息抽取.电子学报.2005,Vol.33(2)：237-241.
[103]应伟勤,李元香,SHEU Phillip C-Y等.演化多目标优化中的几何热力学选择.计算机学报.2010,Vol.33(4)：755-767.
[104]卢致杰,覃正.基于信息网格的智能多代理系统QoS优化研究.计算机工程.2005,V01.31(15)：13-15.
[105]王嫚,徐惠民.基于熵的网格资源QoS优化策略.北京邮电大学学报.2006,V01.29(4)：30-33.
[106]雷博,范九伦.广义模糊熵阈值法中基于粒子群优化的参数选取.控制与决策.2009,Vol.24(3)：446-450.
[107]朱学军,陈彤,薛量,李峻.多个体参与交叉的Pareto多目标遗传算法.电子学报.2001,Vol.29(1)：106-109.
[108]史忠植.高级人工智能(第二版).北京：科学出版社.2006.
[109]Sonmk E J. The Optimal control of partially observable Markov processes over the infinite horizon:Discounted costs. Operations Research,1978, Vol.26(2): 282-304.
[110]Kaelbling L P,Littman M L, Cassandra A R. Planning and acting in partially observable stochastic domains. Artificial Intelligence.1998,101:99-134.
[111]张波,蔡庆生 口语对话系统的POMDP模型及求解.计算机研究与发展,2002,Vol.39(2)：217-224.
[112]Cheng H T. Algorithms for partially observable Markov decision processes. Thesis for Doctor's Degree. Vancouver Columbia:University of British Columbia,1998.
[113]Zhang N L, Zhang W. Speeding up the convergence of value iteration in partially observable Markov decision processes. Journal of Artificial Intelligence Research.2001,Vol.14:29-51.
[114]Cassandra A, Littaman M, Zhang N. Incremental pruning:A simple, fast, exact method for partially observable Markov decision processes. Proceedings of the 13th Annual Conf. on Uncertainty in Artificial Intelligence.1997:54-61.
[115]周继恩,刘贵全.基于内部信念状态POMDP模型在用户兴趣获取中的应用.小型微型计算机系统.2004,Vol.25(11)：1979-1983.
[116]Poupart P. Exploiting structure to efficiently solve large scale partially observable Markov decision processes. Toronto:University of Toronto. 2005.[Online] ww.cs.uwaterloo.ca/-ppoupart/publications/ut-thesis/ut-thesis.ps.
[117]Daniel S Bernstein, Eric A Hansen, Shlomo Zilberstein. Bounded policy iteration for decentralized POMDPs. Edinburgh, Scotland:The Proceedings of the 19th International Joint Conference on Artificial Intelligence. 2005:1287-1292.
[118]Dima B, Michel D R, Anatol S. On the complexity of partially observed Markov decision processes. Theoretical Computer Science,1996, Vol.157(2): 161-183.
[119]Papadimitriou C H, Tsitsiklis J N. The complexity of Markov decision processes. Mathematics of Operations Research.1987,Vol.12(3):441-450.
[120]Littrnan M L, Cassandra A, Kaelbling L. Learning policies for partially observable environments:Scaling up. Proceedings of the Twelfth International Conference on Machine Learning. San Francisco, CA:Morgan Kaufmann Publishers,1995:362-370.
[121]Pineau J, Gordon G Thrun S. Point-based value iteration:an anytime algorithm for POMDPs. Proceedings of International Joint Conference on Artificial Intelligence.2003:1025-1032.