模型法求规划的研究

模型法求规划是一种通用的规划方法。它从给定问题的模型中抽取出规划。本文综述了模型法求规划的基本方法。首先介绍了SATPLAN和CSP，以讨论模型法求规划的通用框架。然后介绍了新近开发的模型法求规划系统，BLACKBOX和GP-CSP。在将模型法与演绎法和CBP法进行比较后，给出了模型法求规划的未来研完方向。     

Adaptive selection of reactive/deliberate planning for a dynamic environment

This paper proposes and evaluates a new real-time reactive planning approach for a dynamic environment. In addition to having the features of conventional real-time reactive planning, which can react in a dynamic environment, our planning can perform deliberate planning appropriately. The proposed planning uses three kinds of agents: behavior agents that control simple behavior, planning agents that make plans to achieve their own goals, and behavior-selection agents that intermediate between behavior agents and planning agents. They coordinate a plan in an emergent way for the planning system as a whole. We confirmed the effectiveness of our planning by means of a simulation. Furthermore, we implemented an active-vision system and used it to verify the real-world efficiency of our planning.     

不确定层次任务网络规划研究综述

层次任务网络(Hierarchical task network, HTN)规划作为一项重要的智能规划技术被广泛应用于实际规划问题中, 传统的HTN规划无法处理不确定规划问题.然而, 现实世界不可避免地存在无法确定或无法预测的信息, 这使许多学者开始关注不确定规划问题, 不确定HTN规划研究也成为HTN规划研究的前沿.本文从HTN规划过程出发分析了不确定HTN规划问题中涉及的三类不确定, 即状态不确定、动作效果不确定和任务分解不确定; 总结了系统状态、动作效果和任务分解等不确定需要扩展确定性HTN规划模型的工作, 以此对现有不确定HTN规划的研究工作加以梳理和归类; 最后,对不确定HTN规划研究中仍需要解决的问题和未来的研究方向作了进一步展望.     

基于粗糙集的智能规划算法的研究

提出一种新的不确定,即初始对象集合的不确定,并利用粗糙集理论来解决这种不确定性;将粗糙集理论和智能规划相结合,提出一种新的不确定规划——粗规划。给出了粗规划问题的概念、粗规划的初始状态、粗糙动作和粗规划目标等一系列相关的定义,提出了粗规划问题的两种求解模型,并给出基于规划图的粗规划算法。     

规划图框架下用遗传算法求解时态规划问题

许多现实世界中的规划问题通常希望规划目标能在尽可能短的时间内实现,并且规划动作的执行需要考虑时间因素.在规划图框架下,提出了一种能进行时态约束推理的遗传规划算法.主要工作有以下3个方面:1)介绍基于完全动作图的时序约束推理技术;2)提出能进行时序约束推理的基于规划图的遗传规划技术;3)针对基于规划图的遗传规划技术存在局部搜索能力不足的缺点,提出了在原有遗传操作算子的基础上,引入局部修复算子的混合规划技术.实验表明,这种算法能有效地处理一类时态规划问题.     

非确定规划及带有时间和资源的规划的研究

智能规划是人工智能近年来的研究热点, 早期的工作主要是围绕着具有较强约束的经典规划展开, 最近的工作放宽了这些假设, 使智能规划逐渐走向应用。在分析经典规划特点的基础上, 介绍了非确定规划的研究进展和带有时间和资源的规划的研究, 并对智能规划的进一步工作和存在的问题提出了一些看法。     

GP——基于规划图的遗传规划算法

图规划是智能规划领域近年来出现的一种新的规划方法,对智能规划的发展有着重要的影响.图规划的规划产生过程分为两个主要步骤,首先用动作的前提条件和效果产生一个谓词和动作交错出现的图--规划图,然后在规划图中抽取规划解.而第二步往往更为困难和耗时.文章依据遗传算法对规划图提出一种新的解抽取方法,以一种简明、直观的形式给出染色体的编码方式,并在此基础上定义了各种遗传操作算子,将遗传算法引入图规划算法,充分利用遗传算法的并行全局搜索能力实现规划解的搜索.实验表明,在求解大规模的规划问题时,文中的遗传规划算法在求解速度和找到的规划解的质量两方面均显示出优越性.     

On the complexity of case-based planning

This paper analyses the computational complexity of problems related to case-based planning: planning when a plan for a similar instance is known, and planning from a library of plans. It is proven that planning from a single case has the same complexity than generative planning (i.e. planning ‘from scratch’); using an extended definition of cases, complexity is reduced if the domain stored in the case is similar to the one to search plans for. Planning from a library of cases is shown to have the same complexity. In both cases, the complexity of planning remains, in the worst case, PSPACE-complete.     

DSMT配电网格模型及其配电网规划体系设计研究

网格及网格化规划是配电网规划的一种新的理念及方法,但从实际应用上看,目前业界对“网格”及“网格化”规划的理解尚未形成真正的共识,对网格的定义、划分原则及基于网格的规划体系也均未给出明确的阐述。据此,我们在吸收国内外主流观点的基础上,通过规划实践,形成了包括电力需求侧、电力供给侧及运行管理三个视角的配电网格化模型;按照配电网格化规划的新理念,采用“先分区”,“后全域”,“再分区”的基本步骤,以先“自下而上”分析,再“自上而下”规划的工作模式,提出科学合理的、可用于实际操作的配电网格化布局规划新方法,呈现实用化规划成果;同时,在对网格特征进行规范化分析的基础上,按照“同类型网格标准化”,“不同类型网格差异化”的原则,实现“标准化”及“差异化”规划目标的融合。并以此为基础,给出了基于网格的配电网统筹规划体系,此规划体系对现行的配电网规划实务产生积极的指导作用。     

Formalizing planning knowledge for hierarchical planning

A hierarchical planning system achieves efficiency by planning with the most important conditions first, and considering details later in the planning process. Few attempts have been made to formalize the structure of the planning knowledge for hierarchical planning. For a given domain, there is usually more than one way to define its planning knowledge. Some of the definitions can lead to efficient planning, while others may not. In this paper, we provide a set of restrictions which defines the relationships between a non-primitive action and its set of subactions. When satisfied, these restrictions guarantee improved efficiency for hierarchical planning. One important feature of these restrictions is that they are syntactic and therefore do not depend on the particular structure of any plan. Along with these restrictions, we also provide algorithms for preprocessing the planning knowledge of a hierarchical planner. When used during planning, the preprocessed operator hierarchies can enable a planner to significantly reduce its search space.     

Automation and optimization in crane lift planning: A critical review

Safe and efficient crane operations play a significant role in successful delivery of construction projects, and thus meticulous planning of crane lifts becomes increasingly critical. Crane lift planning involves a series of complex decisions to be made, while satisfying a wide range of criteria and constraints. Conventionally, making these decisions is time-consuming and to a large extent relies on the planner’s experience. To make more informed and optimized planning decisions, past research works investigated various automated planning techniques and optimization algorithms. However, most studies focus on an individual planning decision or a particular lifting scenario, which makes the findings hard to be generalized. Thus, the knowledge in lift planning is rather fragmented and the state-of-the-art in lift planning is not explicitly presented. This study, therefore, aims to conduct a critical review and assessment on the literature on crane lift planning automation and optimization and to establish a solid foundation to inform future research. It first presents an overview of the literature in crane lift planning with respect to the planning decision and the type of cranes the studies focus on. Secondly, for each lift planning decision, the assumptions, objectives, decision variables, and constraints are formulated based on the literature and analyzed from the perspectives of problem formulation coherence. Furthermore, each problem-solving method is evaluated with regard to a tri-axial evaluation diagram to allow an in-depth discussion on the efficacy and practicality of planning results. Finally, based on the discussion and existing literature, a BIM-based lift planning framework is presented and future research directions are recommended to further improve the effectiveness and efficiency of lift planning practice.     

基于STK/Scheduler的空间天文卫星任务规划研究

空间天文卫星任务规划是一类复杂的NP难问题,将STK/Scheduler(Satellite Tool Kit/ Scheduler,卫星仿真工具包/任务规划)商业软件从对地观测任务规划领域拓展应用至空间天文卫星任务规划领域,对于获取可靠解算结果、快速构建地面运控仿真环境、提供解算参考基准具有重要意义。根据空间天文卫星任务规划问题,建立了以最大获取科学回报为目标的多约束任务规划模型,开展了基于STK/Scheduler的空间天文卫星任务规划解算和实例验证。实验结果表明:利用STK/Scheduler开展空间天文卫星任务规划能够适应多种规划时段和解算要求,具有求解稳定等特点,可以满足空间天文卫星任务规划的基本需求。     

Algorithmic motion planning in robotics

A survey is presented of an approach to motion planning that emphasizes object-oriented, exact, and discrete (or combinatorial) algorithmic techniques in which worst-case asymptotically efficient solutions are being sought. Following a statement of the problem, motion planning in static and known environments is treated. The discussion covers general solutions, lower bounds, the projection method, the retraction method, the expanded obstacles, the single-component approach, and a mobile convex object moving in a 2D polygonal space. Variants of the motion-planning problem are then considered, namely, optimal motion planning, adaptive and exploratory motion planning, motion planning in the presence of moving obstacles, constrained motion planning, motion planning with uncertainty, and general task planning     

Ein Planungsansatz zum Umgang mit Störungen bei der Produktion: Die flexible Produktionsfeinplanung mithilfe von Planungsschritten

Disruptions like the breakdown of machines or delays in the delivery of materials cause generated production plans to be useless, at least in some parts. A new planning approach for coping with this uncertainty caused by disruptions is presented. Planning steps that are described by properties, preconditions and consequences are used for material requirements planning and scheduling. If their preconditions are satisfied in a certain state of environment, planning steps will be applicable. The consequences of planning steps change the state of environment. Each customer order establishes a goal of a new planning problem to be achieved by applying planning steps. Plan execution concerns all planning steps applicable in a certain state of environment. In choosing among applicable planning steps and among available resources the flexibility of plan execution is preserved.     

面向平层多房间的内墙作业移动机器人路径规划

本文针对多房间的移动机器人内墙作业的路径规划任务,提出一种两阶段路径规划方法.第1阶段针对沿墙作业过程中环境存在灰尘或雾气造成的传感器失效问题,以及房间多出口时路径规划不完整问题,我们提出起点自动选择沿墙路径规划方法,基于栅格地图离线生成沿墙规划路径.第2阶段,针对点到点路径规划过程中的动态避障问题,我们提出一种基于PSAC (prioritized experience replay soft actor critic)算法的点到点路径规划方法,在软行动者-评论家(soft actor critic, SAC)的中引入优先级经验回放策略,实现机器人的动态避障.实验部分设计了沿墙路径规划对比实验和动态避障的对比实验,验证本文所提出的方法在室内沿墙路径规划和点到点路径规划的有效性.     

多圆碟形水下滑翔机的双层协调三维路径规划

本文研究了欠驱动圆碟形水下滑翔机集群在海流干扰和水下碍航物影响下的三维路径规划问题. 具体地: 第一, 根据圆碟形水下滑翔机的航行特点, 建立了相应的航行时间模型, 设计了三维路径规划的优化目标; 第二, 提 出了一种基于双层协调的多水下滑翔机三维路径规划结构, 采用基于三维离散空间的全局路径规划和基于人工势 场法的局部路径规划, 避免了滑翔机与碍航物以及不同优先级的滑翔机之间发生碰撞; 第三, 基于双层协调路径规 划结构, 采用基于量子行为的自适应粒子群优化方法完成了时间最优目标下多圆碟形水下滑翔机的三维路径规划. 仿真结果验证了所提多圆碟形水下滑翔机三维路径规划方法的有效性.     

Incremental planning using conceptual graphs

Abstract

When performing a planning or design task in many domains it is often difficult to specify in advance what the precise goals are. It is therefore useful to have a system in which the planning process is performed interactively, with the solution approaching the users' intent incrementally through iterations of the planning process. A planning system intended to function in this way must be able to take goal specifications interactively rather than all at once at the beginning of the planning process. The planning process then becomes one of satisfying new goals as they are given by the user, modifying as little as possible the results of previous planning work. Incremental planning is an approach to interactive planning problems that allows a system to create a plan incrementally, modifying a previous plan to satisfy new or more precise goal specifications. In this paper we present an incremental planning system called the general constraint system (GCS) that is based on the conceptual programming environment (CP) developed at New Mexico State University and we show an example of the use of the system for a simple civil engineering design problem     

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.     

仿人机器人足迹规划建模及算法实现

足迹规划是仿人机器人运动规划领域的一个新思想.本文建立了仿人机器人足迹规划的模型,并通过构建启发式成本函数,利用A*算法予以实现.针对复杂多障碍物环境,特别提出了基于可变落地足迹数量的复合足迹转换模型的方法.仿真实验证明了规划模型和算法的有效性和完备性,规划效果达到仿人机器人在线运动规划的要求.同时,数值实验也证明了在复杂多障碍物环境下复合足迹转换模型的必要性和优越性.