一种求解最小权值强规划的方法

以规划领域中的不确定状态转移系统作为研究对象,给出最小权值强规划解的概念,提出一种求最小权值强规划解的方法.该方法可以求解与动作代价相关的数值规划问题,在不确定状态转移系统的执行动作上增加权值来表示动作的代价,在此基础上设计求解最小权值强规划解的算法.实验结果表明,该算法能有效求解最小权值强规划解,且比用反向搜索方法求...     

PPDDL一致性规划任务的有限域转换方法

给出了PPDDL一致性规划任务和有限域一致性规划任务的定义,扩展了非确定动作等相关语义,并在此基础上提出了一种将PPDDL表示的一致性规划任务转换为有限域表示的一致性规划任务的CFDR方法,实现了经典规划的FDR转换算法在一致性规划中的扩展。相比MCPT算法,主要改进了其中的合成不变量方法和任务生成方法,此外还增加了对于非确定动作效果的表示和处理。通过在标准的一致性规划域上的实验,证明了CFDR的适用性和有效性。     

不确定规划中的多Agent带权值强规化算法

在智能规划领域中,以往对不确定规划问题的研究主要集中于单个Agent,而对多Agent规划的研究则侧重于确定规划。针对该问题,提出基于多Agent的带权值不确定规划问题,对所求解的强规划解,设计使其所需动作权值总和近似最小的算法。根据基于模型检测的强规划分层方法,对每个Agent进行强规划分层,合并所有Agent的分层信息,并在合并的过程中得到同层状态之间的冲突表。在保证冲突最小的情况下,以最小动作权值优先的贪心方法,求出强规划解。实验结果表明,该算法能较快地求解出使所选择的动作权值总和近似最小的强规划解。     

基于多值表示的并行规划方法

Fast Downward规划系统是第四届国际规划竞赛的冠军.以高效的串行规划系统Fast Downward为基础,设计并实现了并行规划系统Parallel Downward.首先提出4个并行规划的相关定义;之后提出多值规划任务下动作互斥的定义、充要条件,并实现了动作互斥判断算法;在此基础上设计了候选并行动作集的生成算法;然后为提高系统求解质量重新设计了新的搜索控制策略;最后,给出剪枝策略来抑制并行规划状态空间的指数级膨胀.通过对国际规划竞赛测试问题的实验,Parallel Downward表现出良好的规划效率和规划质量,相比Sapa规划系统Parallel Downward具有较好的可扩展性.     

不确定可逆规划的强循环规划解

动作的执行在理想情况下是确定的,但现实生活中常常因为意外情况的发生而造成了不确定性,并产生不利影响.针对这种情况,建立了一种新的不确定规划模型,在不确定规划中增加了两个约束:1)所有动作的执行是可逆的;2)若一个状态在理想情况下不能达到目标,那么它不能企图在执行一个动作时发生意外而接近或达到目标.在该模型下设计了求解强循环规划的算法,首先只考虑所有动作的执行是在理想情况下发生的,这时可以将规划子图转换为规划子树并求出规划子树中每个状态的可达性;接下来考虑所有动作执行意外的情况,若动作被意外执行之后不能到达目标状态,则删除这个动作并更新规划子图和规划子树,最后通过遍历规划子图和规划子树求强循环规划解.考虑到有些意外的发生并不可预知,该算法能够在意外发生时只对部分失效的规划解进行更新而不需要重新求规划解.实验结果证明该算法能够快速地更新规划解且与问题的规模大小无关.     

分层法求最小权值强规划解

在不确定规划领域中,以往对强规划解的研究侧重于解本身,很少考虑不确定转移系统执行动作所需的代价;而已有的研究最小权值强规划解的算法效率不高。针对这一问题,引入模型检测的强规划分层方法,设计了一种快速求解最小权值强规划解的算法。该算法首先将不确定规划问题中的状态进行强规划分层,然后利用分层信息反向搜索最小权值强规划解;且在搜索的过程中,根据算法策略,实时更新所需搜索层数的上界和下界,从而避免了大量的无用搜索,提高了搜索效率。实验表明:所设计的算法能快速求解出最小权值强规划解,求解效率比已有的直接求解最小权值强规划解的算法高;且分层数和动作数越大,优势越明显。     

不确定规划中可达关系的快速求解算法

在不确定规划领域中,通常需要在同一个不确定状态转移系统中解决多个规划问题,如果能得到不确定规划中状态之间的可达关系即可方便求解该规划问题,然而现有矩阵乘法求解可达关系时存在算法复杂度高的问题。为此,设计一种快速求解不确定规划中状态之间可达关系的算法,将确定动作和不确定动作区分处理,先求解所有确定动作的可达关系,再采用链表和队列求解不确定动作的可达关系。实验结果表明,与矩阵乘法相比,该算法能得到更全面的可达关系,且求解效率更高。     

基于延迟部分推理的快速前向规划系统

根据动作组件诱发关系的存在和抵制计算的必要性,提出一个计算松弛规划解的新方法——延迟部分推理.该方法在考虑动作删除效果的假定下,构造不包含任何互斥关系的组件规划图,通过定义"松弛诱发"关系预测后续规划过程中可能出现的组件诱发现象,在松弛规划解提取阶段判断动作组件间的"松弛诱发"关系并选择抵制动作避免可能发生的消极作用.基于延迟部分推理方法定义了新的启发式函数和剪枝策略,设计了规划系统FFc并在多个国际通用的测试域上进行实验.结果表明,FFc较之Fast-Forward在求解效率和求解质量方面都有显著的提高.     

分层法求强循环规划解

设计了一种求解强循环规划问题的状态分层算法。从目标状态开始,首先进行强规划分层,然后对剩余状态进行弱规划分层,并记录相应信息,最后用该信息作启发因子,在弱规划分层结果中搜索强循环规划分层。分层结束后利用分层时记录的信息可以直接得到强循环规划解。所设计的算法在求解状态动作较多的强循环规划问题时有较高的效率;且当强规划解存在时,求解效率更高,并能保证得到质量更优的强循环规划解——强规划解。实验表明,所设计的算法能够以较少的重复搜索得到强循环规划解,求解效率比反向搜索高。     

最小化全局完成时间的成像卫星任务规划算法

成像侦察卫星任务规划问题是一类典型多约束组合优化问题.最小化全局完成时间是任务规划领域时效性要求较高情况下的一种优化目标.提出一种整合整数规划与约束规划方法,在最小化任务规划方案全局完成时间的目标下,求解成像侦察卫星任务规划问题的组合算法.该算法通过应用Benders分解将原约束整数规划模型划分为主问题与子问题两部分,采用软件MOSEK与GECODE对主、子问题分别求解.根据子问题求解结果生成剪枝约束,返回主问题迭代,直到获得优化解.算法有效性通过仿真实验进行了检验并取得预期效果.     

基于单逻辑程序的一致性规划任务有限域表示方法

有限域表示(FDR)能有效地压缩状态空间, 其转换算法在实例化阶段对每个初始状态都生成一个逻辑程序, 而一致性规划任务的初始状态数量通常较大, 所以这通常需要较大的时间和空间开销, 甚至导致内存溢出。为了提高转换算法运行效率使其能处理更为复杂的规划问题, 提出了一种基于单逻辑程序的IFDR转换算法。IFDR算法从初始信念状态中所有可能的初始世界状态得到一个事实集, 再由动作和公理计算得到一个规则集。一个事实集和一个规则集组成一个逻辑程序, IFDR用此单逻辑程序完成实例化。实验结果表明IFDR算法在解决问题的效率和数量上都有所提高。     

基于扩展状态任务网的制造供应链计划

制造供应链计划是制造供应链管理的关键问题,它不仅需要分配生产任务和控制库存,还需要解决不同工厂(企业)间的运输配套问题.为统一描述具有复杂产品生产过程(包括装配型、分解型和多输入多输出型等)的生产任务、存储任务和不同模式(包括单种物料独立运输模式和多种物料组合运输模式)的运输任务,提出了扩展状态任务网(extended state task network,简称ESTN).扩展状态任务网用比例转化任务统一描述生产任务、存储任务和单种物料独立运输任务,用虚比例转化任务和组合移动任务共同描述多种物料组合运输任务.应用扩展状态任务网,meta启发式方法在求解制造供应链问题时更容易编码和操作.为求解基于ESTN的制造供应链计划模型,提出了具有多样性检测的参考解集更新策略与分散性解变异策略的路径重连算法.路径重连算法维护一个由高质量解(精英解)组成的参考解集,将一个向导精英解的属性逐步引入一个起始精英解而形成的中间解序列(路径),并用此中间解序列更新参考解集以获得进化.计算实例表明,该路径重连算法比标准遗传算法、标准Tabu搜索算法以及普通路径重连算法能够获得更好的解,证明了多样性检测对参考解集更新的关键作用以及分散性解变异策略在提高解的质量上的能力.     

一种优化的一致性规划状态变量选择算法

研究了一致性规划任务信念状态空间的表示方法。针对一致性有限域表示(CPT-FDR)算法在任务生成阶段选择状态变量的不足,提出了一种基于初始状态中文字相容互斥的状态变量选择算法——MECV算法。CPT-FDR未考虑初始信念状态中文字的互斥性,产生冗余的编码信息,降低了编码的效率。MECV算法利用有用正负文字构造新的未覆盖事实集,提取初始信念状态中处于不同世界状态的文字组成互斥组,再编码状态变量。实验结果表明该算法能有效地压缩信念状态空间。     

Learning Hierarchical Task Models from Input Traces

We describe HTN‐MAKER , an algorithm for learning hierarchical planning knowledge in the form of task‐reduction methods for hierarchical task networks (HTNs). HTN‐MAKER takes as input a set of planning states from a classical planning domain and plans that are applicable to those states, as well as a set of semantically annotated tasks to be accomplished. The algorithm analyzes this semantic information to determine which portion of the input plans accomplishes a particular task and constructs task‐reduction methods based on those analyses. We present theoretical results showing that HTN‐MAKER is sound and complete. Our experiments in five well‐known planning domains confirm the theoretical results and demonstrate convergence toward a set of HTN methods that can be used to solve any problem expressible as a classical planning problem in that domain, relative to a set of goal types for which tasks have been defined. In three of the five domains, HTN planning with the learned methods scales much better than a modern classical planner.     

Conformant planning via heuristic forward search: A new approach

Conformant planning is the task of generating plans given uncertainty about the initial state and action effects, and without any sensing capabilities during plan execution. The plan should be successful regardless of which particular initial world we start from. It is well known that conformant planning can be transformed into a search problem in belief space, the space whose elements are sets of possible worlds. We introduce a new representation of that search space, replacing the need to store sets of possible worlds with a need to reason about the effects of action sequences. The reasoning is done by implication tests on propositional formulas in conjunctive normal form (CNF) that capture the action sequence semantics. Based on this approach, we extend the classical heuristic forward-search planning system FF to the conformant setting. The key to this extension is an appropriate extension of the relaxation that underlies FF's heuristic function, and of FF's machinery for solving relaxed planning problems: the extended machinery includes a stronger form of the CNF implication tests that we use to reason about the effects of action sequences. Our experimental evaluation shows the resulting planning system to be superior to the state-of-the-art conformant planners MBP, KACMBP, and GPT in a variety of benchmark domains.     

基于多智能体强化学习的微装配任务规划方法

现有装配任务规划方式多为人工规划，存在低效、高成本、易误操作等问题，为此分析了微装配操作的任务特点，以及对微装配中多操作臂协作与竞争关系进行了详细分析，并提出多智能体强化学习中符合微装配任务特点的动作空间、状态空间以及奖励函数的构建方法；利用CoppeliaSim仿真软件构建合理的仿真模型，对已有设备进行物理建模，构建了基于多智能体深度确定性策略梯度算法的学习模型并进行训练，在仿真环境中对设计的状态、动作空间以及奖励函数进行了逐项实验验证，最终获得了稳定的路径以及完整的任务实施方案；仿真结果表明，提出的环境构建方法，更契合直角坐标运动为主要框架的微装配任务，能够克服现有规划方法的不足，能够实现可实际工程化的多臂协同操作，提高任务的效率以及规划的自动化程度。     

基于模态逻辑D公理系统的Conformant规划方法

2006年,conformant规划问题成为国际规划竞赛不确定性问题域中的标准测试问题,得到研究人员的广泛关注.目前,conformant规划系统都是将其看成信念状态空间上的启发式搜索问题予以求解.通过分析conformant规划问题的语法和语义,提出新的基于模态逻辑的规划框架.将其转换为模态逻辑D公理系统的一系列定理证明问题.提出2种基于模态逻辑的编码方式.构造相应的公理与推理规则形成模态公式集,保证对于D系统的定理证明过程等同于原问题的规划过程.并通过问题实例验证该方法的有效性.继基于SAT、CSP、线性规划、模型检测等求解技术的规划方法后,该规划框架是基于转换的规划方法的一种新的尝试.     

State agnostic planning graphs: deterministic,non-deterministic,and probabilistic planning

Planning graphs have been shown to be a rich source of heuristic information for many kinds of planners. In many cases, planners must compute a planning graph for each element of a set of states, and the naive technique enumerates the graphs individually. This is equivalent to solving a multiple-source shortest path problem by iterating a single-source algorithm over each source.We introduce a data-structure, the state agnostic planning graph, that directly solves the multiple-source problem for the relaxation introduced by planning graphs. The technique can also be characterized as exploiting the overlap present in sets of planning graphs. For the purpose of exposition, we first present the technique in deterministic (classical) planning to capture a set of planning graphs used in forward chaining search. A more prominent application of this technique is in conformant and conditional planning (i.e., search in belief state space), where each search node utilizes a set of planning graphs; an optimization to exploit state overlap between belief states collapses the set of sets of planning graphs to a single set. We describe another extension in conformant probabilistic planning that reuses planning graph samples of probabilistic action outcomes across search nodes to otherwise curb the inherent prediction cost associated with handling probabilistic actions. Finally, we show how to extract a state agnostic relaxed plan that implicitly solves the relaxed planning problem in each of the planning graphs represented by the state agnostic planning graph and reduces each heuristic evaluation to counting the relevant actions in the state agnostic relaxed plan. Our experimental evaluation (using many existing International Planning Competition problems from classical and non-deterministic conformant tracks) quantifies each of these performance boosts, and demonstrates that heuristic belief state space progression planning using our technique is competitive with the state of the art.     

基于状态空间的机械臂轨迹规划

提出一种基于状态空间的机械臂轨迹规划方法,定义并构造了机械臂系统的状态空间,根据内在机构约束与外部环境约束描述出系统状态的可达范围,并给出了任务的可实现条件.对于可实现任务,在状态空间能搜索到任务完成的最优解.如果任务无法完成,则修改系统配置或约束,在新的状态空间确定任务实现的转化条件,并对任务的设计与规划给予指导.研究了障碍约束下两连杆机械臂的点到点任务,实验结果验证了该方法的有效性.