一类非线性两层规划问题的递阶优化解法

提出一种求解一类非线性两层规划问题的新方法．通过引入解耦向量将非线性两层规划问题分解为独立且易于求解的子问题，利用两级递阶结构第1级求解若干优化的子问题，而在第2级利用第1级求解的结果调整解耦向量．所提出的方法借助于分解一协调原理并按迭代方式最终求得问题的最优解．对于含整数的规划问题，通过连续化处理后也可按该方法方便地求解．算例表明所提出的算法是简便而有效的．     

基于递阶嵌套GA 的空-地武器靶场效能大规模总体优化

针对大规模优化问题，其大系统分解协调算法存在收敛速度慢、计算时间长、易导致组合爆炸等不足，以空-地制导武器大规模火力规划问题为背景，提出一种递阶嵌套GA．其基本思想是通过分层降低计算复杂性，从而有效解决大规模火力规划问题求解的可计算性问题．递阶嵌套GA由内外两层构成。内层GA实现对各子模型的求解，并将求解结果传送给外层GA；外层GA则通过遗传操作对内层GA发生干预．仿真算例验证了算法的有效性．     

基于任务分解与强化学习的多平台协同火力分配方法

为了有效求解多平台协同火力分配问题,根据“分而治之”的思想,基于任务分解策略将复杂的决策任务分解为子目标平台选择和子平台火力分配两个阶段,通过融合启发式算法和强化学习模型,提出一种新的强化学习求解方法(HARL),并以多平台联合火力打击为作战背景进行实验仿真.子目标平台选择层根据当前状态,基于强化学习策略选择攻击当前子目标最适合的火力平台;而子平台火力分配层则使用启发式算法为执行攻击任务的平台规划最优的火力分配方案.实验结果表明,融合启发式算法和强化学习的HARL方法相比于传统的强化学习算法武器消耗量减少15%以上,相比于经典的启发式算法求解时效性提升20%以上,表明该研究成果可为未来求解复杂作战决策问题提供有力的技术支持.     

用非线性分层策略生成机器人动作规划

分层策略可以求解复杂的机器人规划生成问题.本文提出一种崭新的分层规划算法,该算法将原问题分解为若干子问题,然后按各层的动作细化规则,由顶而底.直至求出机器人的本原动作序列.在每个层次上,运用非线性技术,使之对子问题的求解可交叉进行,从而消除了目标相互影响问题;在规划动作的过程中,建立了前后指针和评价函数,并提出了解决分层规划中动作的冗余和矛盾的方法,大大地提高了解题效率.该算法已应用于 NARP机器人规划生成系统,本文简介了用 Common Lisp 语言编程的特点.系统在 Sun 机上实现.     

基于路标隐式分解的前向搜索规划方法

提出一种利用路标信息隐式分解前向搜索过程的规划算法。以路标计数启发式估值的降低作为分界点,将规划任务分解成多个规模更小的子任务,当访问到估值更低的状态时,表明搜索过程完成一个子任务的求解,反复执行这一过程直到路标计数启发式估值降低为零。与其它将路标具体指定为中间目标的分解方法相比,基于路标计数启发式的隐式分解方法能指导前向搜索过程快速向目标方向推进,实现搜索空间的大规模压缩,在求解效率和规划解质量上都有较大提高。     

基于聚类分解的WCDMA基站布局规划算法

针对大规模WCDMA无线网络基站布局规划问题,提出一种基于聚类分解的分层算法．在聚类分解中,以测试点信号增益矩阵构造聚类分解数据,并给出了收敛判定函数和相似度计算方法．在分层算法中,首先用K均值聚类将原问题分解为K个子规划问题,然后对各子问题求解整数规划问题,最后对各子问题的基站布局结果进行全局调整．仿真计算验证了该算法的有效性．     

面向多目标流水车间调度的多种群多目标遗传算法

针对制造型企业普遍存在的流水车间调度问题,建立了以最小化最迟完成时间和总延迟时间为目标的多目标调度模型,并提出一种基于分解方法的多种群多目标遗传算法进行求解.该算法将多目标流水车间调度问题分解为多个单目标子问题,并分阶段地将这些子问题引入到算法迭代过程进行求解.算法在每次迭代时,依据种群的分布情况选择各子问题的最好解及与其相似的个体分别为当前求解的子问题构造子种群,通过多种群的进化完成对多个子问题最优解的并行搜索.通过对标准测试算例进行仿真实验,结果表明所提出的算法在求解该问题上能够获得较好的非支配解集.     

多机器人不确定协作任务的动态优化方法

针对一类可变目标的多机器人协作运动问题，提出动态优化的方案．在每一优化时刻 根据当前目标状态及其变化规律，确定每个机器人的运动，得到该时刻概率意义上的最优运 动．把系统整体路径规划的复杂问题分解为独立路径规划问题和分派问题分别求解，实现最 快协作运动．并且将这种优化方案动态实施，以适应目标的不确定性．提出的方法还可推广 到更一般的不确定协作任务中．     

基于任务分解结构的供应链合作伙伴优化选择

为实现虚拟企业供应链构建中的多目标合作伙伴优化选择，根据任务完成的交货期、质量、成本和服务四个评价指标，利用总任务下各评价指标的权重以及在每个评价指标下各子任务之间的关联特性,建立了基于任务分解结构的供应链伙伴选择多目标决策模型。基于该模型实现了分解任务完成时间的定量计算，给出了基于自适应遗传算法模型求解方法，并应用实例验证了该模型和算法的有效性。     

基于协同进化博弈的多学科设计优化

复杂系统的设计问题可以非层次分解为并行的多个子空间优化设计问题。多学科优化的迭代过程可看成子空间博弈的过程。各冲突子目标协商一致条件下,子空间合作博弈的均衡点能达成原系统的整体最优,并给出协同进化算法求解博弈的Nash均衡点的计算框架。以某型民用客机的总体优化设计为例,将其分解成气动和重量两个子空间优化。设计变量不重叠地分布于各子空间,两冲突子目标分配相同权值,线性加权组合而形成的单目标作为各子空间共同的优化目标。计算结果表明此方法是有效的。     

Problem representation for refinement

In this paper we attempt to develop a problem representation technique which enables the decomposition of a problem into subproblems such that their solution in sequence constitutes a strategy for solving the problem. An important issue here is that the subproblems generated should be easier than the main problem. We propose to represent a set of problem states by a statement which is true for all the members of the set. A statement itself is just a set of atomic statements which are binary predicates on state variables. Then, the statement representing the set of goal states can be partitioned into its subsets each of which becomes a subgoal of the resulting strategy. The techniques involved in partitioning a goal into its subgoals are presented with examples.     

A planning model with problem analysis and operator hierarchy

A planning model described in terms of its goal analysis and hierarchical operator representation is presented. With this system, successful plans have been made for nonlinear problems that are described as a conjunction of subgoals. The system uses heuristic rules to analyze the problem, and thus achieves an ordered sequence of subgoals and constraints that can be achieved successively without interfering with each other. The operators are designed in a goal-oriented fashion and are stored in operator hierarchies. During the plan generation phase, each subgoal is mapped into a goal operator, which is further refined to meet details and specific conditions of the problem. As the generation phase follows the analysis, conflicts among subgoals are eliminated implicitly     

A meta-planning model for diminishing resource problems

We present a planning and meta-planning model for an important sub-class of the general planning problem. There is a fixed amount of initial resource which monotonically diminishes throughout the planning process. Assuming all subgoals must be achieved, we have created a commonsense meta-planning methodology based on two policies, graceful retreat and least impact, which have the spirit of cooperation among subgoals in making commitments. Graceful retreat allows the most critical subgoal to be achieved first, at the expense of taking some resource potentially useful to some less critical subgoals. Least impact selects the subplan, to achieve that critical subgoal, which uses resource judged least critical to as yet unachieved subgoals.     

Pattern Databases

The efficiency of A* searching depends on the quality of the lower bound estimates of the solution cost. Pattern databases enumerate all possible subgoals required by any solution, subject to constraints on the subgoal size. Each subgoal in the database provides a tight lower bound on the cost of achieving it. For a given state in the search space, all possible subgoals are looked up in the pattern database, with the maximum cost over all lookups being the lower bound. For sliding tile puzzles, the database enumerates all possible patterns containing N tiles and, for each one, contains a lower bound on the distance to correctly move all N tiles into their correct final location. For the 15-Puzzle, iterative-deepening A* with pattern databases(N ="8) reduces the total number of nodes searched on a standard problem set of 100 positions by over 1000‐fold.     

Dynamic reordering of alternatives for definite logic programs

Due to their highly declarative nature and efficiency, tabled logic programming systems have been applied to solving many complex problems. Tabled logic programming is essential for extending traditional logic programming with tabled resolution. In this paper, we propose a new tabled resolution scheme, called dynamic reordering of alternatives (DRA) resolution, for definite logic programs. The scheme keeps track of the type of the subgoals during resolution; if the subgoal in the current resolvent is a variant of a former tabled subgoal, tabled answers are used to resolve the subgoal; otherwise, program clauses are used similar to SLD resolution. Program clauses leading to variant subgoals at runtime are dynamically reordered for further computation until the subgoals are completely evaluated. DRA resolution allows query evaluation to be performed in a depth-first, left-to-right traversal order similar to Prolog-typed SLD resolution, thus yielding a simple technique for incorporating tabled resolution in traditional logic programming systems. We show the correctness of DRA resolution.     

面向Option的k-聚类Subgoal发现算法

在学习过程中自动发现有用的Subgoal并创建Option,对提高强化学习的学习性能有着重要意义.提出了一种基于k-聚类的Subgoal自动发现算法,该算法能通过对在线获取的少量路径数据进行聚类的方法抽取出Subgoal.实验表明,该算法能有效地发现所有符合要求的Subgoal,与Q-学习和基于多样性密度的强化学习算法相比,用该算法发现Subgoal并创建Option的强化学习算法能有效提高Agent的学习速度.     

基于内在奖励的技能获取和组合方法

现有的内在奖励随着agent不断探索环境而逐渐消失,导致了agent无法利用内在奖励信号去指引agent寻找最优策略。为了解决这个问题,提出了一种基于内在奖励的技能获取和组合方法。该方法首先在agent与环境交互过程中寻找积极状态,在积极状态中筛选子目标;其次从初始状态到达子目标,子目标到达终止状态所产生的一条轨迹中发现技能,对技能中出现一个或者两个以上的子目标进行组合;最后用初始状态到子目标的距离和初始状态到子目标的累积奖励值对技能进行评估。该方法在Mujoco环境中取得了较高的平均奖励值,尤其是在外在奖励延迟的情况下,也能取得较好的平均奖励值。说明该方法提出的子目标和技能可以有效地解决内在奖励消失后,agent无法利用内在奖励信号学习最优策略的问题。     

Planning as search: A quantitative approach

We present the thesis that planning can be viewed as problem-solving search using subgoals, macro-operators, and abstraction as knowledge sources. Our goal is to quantify problem-solving performance using these sources of knowledge. New results include the identification of subgoal distance as a fundamental measure of problem difficulty, a multiplicative time-space tradeoff for macro-operators, and an analysis of abstraction which concludes that abstraction hierarchies can reduce exponential problems to linear complexity.     

Dynamic generation of subgoals for autonomous mobile robots usinglocal feedback information

An algorithm is presented for using a local feedback information to generate subgoals for driving an autonomous mobile robot (AMR) along a collision-free trajectory to a goal. The subgoals section algorithm (SSA) updates subgoal positions while the AMR is moving so that continuous motion is achieved without stopping to replan a path when new sensor data becomes available. Assuming a finite number of polynomial obstacles (i.e. the internal representation of the local environment in terms of a 2-D map with linear obstacles boundaries) and a dynamic steering control algorithm (SCA) capable of driving the AMR to safe subgoals, it is shown that the feedback algorithm for subgoal selection will direct the AMR along a collision-free trajectory to the final goal in finite time. Properties of the algorithm are illustrated by simulation examples     

A Pattern-Weight Formulation of Search Knowledge

Pattern-weight pairs (PWs) are a new form of search and planning knowledge. PWs are predicates over states coupled with a least upper bound on the distance from any state satisfying that predicate to any goal state. The relationship of PWs to more traditional forms of search knowledge is explored with emphasis on macros and subgoals. It is shown how PWs may be used to overcome some of the difficulties associated with macro-tables and lead to shorter solution paths without replanning. An algorithm is given for converting a macro-table to a more powerful PW set. Superiority over the Squeeze algorithm is demonstrated. It is also shown how PWs provide a mechanism for achieving dynamic subgoaling through the combination of knowledge from multiple alternative subgoal sequences. The flexibility and execution time reasoning provided by PWs may have significant use in reactive domains. The main cost associated with PWs is the cost of applying them at execution time. An associative retrieval algorithm is given that expedites this matching-evaluation process. Empirical results are provided which demonstrate asymptotically improving performance with problem size of the PW technique over macro-tables.