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.     

Planning with Multistep Forward Search with Forced Goal‐Ordering Constraints

To solve a real‐world planning problem with interfering subgoals, it is essential to perform early detection of subgoal dependencies and achieve the subgoals in the correct order. This is also the case for planning problems with forced goal‐ordering (FGO) constraints. In automated planning, forward search with FGO constraints has been proposed many times over the years, but there are still major difficulties in realizing these FGOs in plan generation. Many existing methods such as goal agenda manager and ordered landmarks cannot detect the FGOs accurately, and thus, the undiscovered ordering relationship may cause the forward search to suffer from deadlocks. In this article, we put forward an approach via an effective search heuristic to constrain a planner to satisfy the FGOs. We make use of an atomic goal‐achievement graph in a look‐ahead search under the FGO constraints. This allows a forward search strategy to plan forward efficiently in multiple steps toward a goal state along a search path. Experimental results illustrate that, by avoiding deadlocks, we can solve more benchmark planning problems more efficiently than previous approaches. We also prove several formal properties for search that are related to FGO detection.     

A simplified problem reduction format

Some new approaches to mechanical theorem proving in the first-order predicate calculus are presented. These are based on a natural deduction system which can be used to show that a set of clauses is inconsistent. This natural deduction system distinguishes positive from negative literals and treats clauses having 0, 1, and 2 or more positive literals in three separate ways. Several such systems are presented. The systems are complete and relatively simple and allow a goal to be decomposed into subgoals, and solutions to the subgoals can then be searched for in the same way. Also, the systems permit a natural use of semantic information to delete unachievable subgoals. The goal-subgoal structure of these systems should allow much of the current artificial intelligence methodology to be applied to mechanical theorem proving.     

基于演化Agent的推理模型

本文描述了一种基于演化 agent的推理模型 ,并用这种推理模型来处理定理机器证明 .传统上 ,定理机器证明常常使用某种逻辑表示 ,然后再进行推理 ,这些方法往往缺乏灵活性 ,且证明过程难以理解 .在本文所叙述的方法中 ,演化 agent能将目标即待证定理分解成越来越小且越来越容易证明的子目标 ,最后完成定理证明 .这种方法非常类似于人类在证明定理时一般所采用的思维方式 ,因而 ,显得更灵活、更具有适应性     

Disjoint pattern database heuristics

We describe a new technique for designing more accurate admissible heuristic evaluation functions, based on pattern databases [J. Culberson, J. Schaeffer, Comput. Intelligence 14 (3) (1998) 318–334]. While many heuristics, such as Manhattan distance, compute the cost of solving individual subgoals independently, pattern databases consider the cost of solving multiple subgoals simultaneously. Existing work on pattern databases allows combining values from different pattern databases by taking their maximum. If the subgoals can be divided into disjoint subsets so that each operator only affects subgoals in one subset, then we can add the pattern-database values for each subset, resulting in a more accurate admissible heuristic function. We used this technique to improve performance on the Fifteen Puzzle by a factor of over 2000, and to find optimal solutions to 50 random instances of the Twenty-Four Puzzle.     

利用算符分析的问题求解

将状态空间的问题求解过程变换为逐步缩小与目标状态的差异过程是一种问题的分解方式．求解差异的顺序可通过分析算符对状态的影响而作出规划，规划的原则是最大限度地在不改变最近已实现子目标的条件下实现下一子目标．为此，在问题分解时各层子目标选择的依据是让各算符有最大的可利用率，即以状态对算符最小约束传播的原则选择各层子目标；最后生成一个子目标规划层次集．问题求解过程就表现为从初始状态开始实现层次集中的某一子目标序列，其间可能涉及子目标回溯．     

The post-game analysis framework-developing resource managementstrategies for concurrent systems

Research has been conducted to determine how distributed computations can be mapped to multiprocessors to minimize execution time. The approach described here, known as post-game analysis, incrementally changes the program partitioning in between program execution time in subsequent runs. Post-game analysis differs from conventional iterative refinement or controlled opportunistic perturbation in that no abstract program models or any single objective function are employed to determine the relative merits of two alternative mappings. Multiple optimization subgoals are formulated, based on actual timing data gathered during program execution. Heuristics, based on various optimization subgoals, are then applied to propose changes to the current mapping. Finally, a mapping generation process which prioritizes and resolves conflicting proposals is applied. Results obtained from simulations show that post-game analysis consistently out-performs random placement, load-balancing, and clustering algorithms by 15%. Few iterations are required for simulations involving more than 200 processes and 64 sites. A rule-based architecture enables incremental strategy refinement, thus making post-game analysis easily tailorable to programs written in many concurrent programming paradigms and multiprocessor architectures     

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.     

一种基于抗体网络的免疫算法

阐述了免疫系统抗体网络的机理和特点,深入分析了抗体网络与常用的免疫算法和Hopfield神经网络异同.通过不断更新输入模式(抗原)和采用最优保存策略,将基于克隆选择的竞争学习算子、自动生成网络结构、剪枝算子和低频变异用于进化操作,提出一种新的基于抗体网络的免疫算法,用于函数优化问题.实验结果表明新算法可行有效.与常用的免疫算法、Hopfield神经网络优化算法比较,新算法具有较好的全局搜索能力和较快收敛速度.     

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     

Explanation-Based Scenario Generation for Reactive System Models

Reactive systems control many useful and complex real-world devices. Tool-supported specification modeling helps software engineers design such systems correctly. One such tool, a scenario generator, constructs an input event sequence for the spec model that reaches a state satisfying given criteria. It can uncover counterexamples to desired safety properties, explain feature interactions in concrete terms to requirements analysts, and even provide online help to end users learning how to use a system. However, while exhaustive search algorithms such as model checkers work in limited cases, the problem is highly intractable for the functionally rich models that correspond naturally to complex systems engineers wish to design. This paper describes a novel heuristic approach to the problem that is applicable to a large class of infinite state reactive systems. The key idea is to piece together scenarios that achieve subgoals into a single scenario achieving the conjunction of the subgoals. The scenarios are mined from a library captured independently during requirements acquisition. Explanation-based generalization then abstracts them so they may be coinstantiated and interleaved. The approach is implemented, and I present the results of applying the tool to 63 scenario generation problems arising from a case study of telephony feature validation.     

A sequent-style model elimination strategy and a positive refinement

We present a sequent style proof system related to the MESON procedure, which is itself based on the model elimination strategy for mechanical theorem proving. The MESON procedure is attractive because it is a problem reduction format, that is, it has a goal-subgoal structure. The sequent style system based on it shares this advantage, and also has a simple declarative semantics and soundness proof. A refinement of the sequent style system tends to produce shorter sequents and may facilitate the use of the MESON procedure with caching of solutions to subgoals to avoid repeated work on the same subgoal. In the MESON procedure, a goal is marked contradicted and considered to be solved, if an ancestor goal is complementary to it. In the positive refinement, only the positive goals need to be checked for contradiction in this way. This means that if a list of ancestor goals is kept with each goal, it is only necessary to store the negative ancestor goals, since these are the only ones that need to be examined in testing if a positive goal is contradicted. Similar restrictions on the reduction operation of model elimination are possible.This research was supported in part by the National Science Foundation under grant DCR-8516243.     

Macro-operators: A weak method for learning

This article explores the idea of learning efficient strategies for solving problems by searching for macro-operators. A macro-operator, or macro for short, is simply a sequence of operators chosen from the primitive operators of a problem. The technique is particularly useful for problems with non-serializable subgoals, such as Rubik's Cube, for which other weak methods fail. Both a problem-solving program and a learning program are described in detail. The performance of these programs is analyzed in terms of the number of macros required to solve all problem instances, the length of the resulting solutions (expressed as the number of primitive moves), and the amount of time necessary to learn the macros. In addition, a theory of why the method works, and a characterization of the range of problems for which it is useful are presented. The theory introduces a new type of problem structure called operator decomposability. Finally, it is concluded that the macro technique is a new kind of weak method, a method for learning as opposed to problem solving.     

问题的有序分解及中转站网络

本文形式地定义了问题的有序分解,并采用导通率和导通分支系数衡量子目标之间的交互作用,为实际中如何选定子目标提供了一种定量的标准,进一步,本文还论述了如何建立中转站网络,它是一种网络结构的有序分解,且更具有应用潜力。最后本文还给出了一个利用这种网络的搜索算法T_w。     

An intelligent hybrid system for surface coal mine safety analysis

Analysis of safety in surface coal mines represents a very complex process. Published studies on mine safety analysis are usually based on research related to accidents statistics and hazard identification with risk assessment within the mining industry. Discussion in this paper is focused on the application of AI methods in the analysis of safety in mining environment. Complexity of the subject matter requires a high level of expert knowledge and great experience. The solution was found in the creation of a hybrid system PROTECTOR, whose knowledge base represents a formalization of the expert knowledge in the mine safety field. The main goal of the system is the estimation of mining environment as one of the significant components of general safety state in a mine. This global goal is subdivided into a hierarchical structure of subgoals where each subgoal can be viewed as the estimation of a set of parameters (gas, dust, climate, noise, vibration, illumination, geotechnical hazard) which determine the general mine safety state and category of hazard in mining environment. Both the hybrid nature of the system and the possibilities it offers are illustrated through a case study using field data related to an existing Serbian surface coal mine.     

Expert systems applied to the analysis of key management schemes

This paper proposes the use of rule based systems, as an aid to system designers, for a study of potential attacks on key management schemes. This approach encourages the designer to consider the system from the attacker's viewpoint and to experiment with a model of the system to examine potential areas of vulnerability. A rule based model of the system is developed and the model is run with inputs comprising details of the information available to the attacker, e.g. plaintext and ciphertext messages that can be tapped etc. The attacker specifies the goal of the attack, e.g. knowledge of a transaction key; the rule based system seeks subgoals which, if satisfied, could lead to the attainment of the goal. In general, the goal cannot be attained, under normal operating circumstances, but the list of subgoals produced can identify information which would be of use to the attacker. This enables the designer to focus attention on specific aspects of the system. The designer can also experiment with the system by postulating that the attacker has gained certain secret information, and testing whether or not this information could enable the attacker to attain the ultimate goal. In addition, the designer can investigate the effect of special circumstances, e.g. appearance of DES semiweak keys or modifications to the system, by suitable additions or modifications to the production of the rule based system. Two systems are studied using the technique, the IBM key management scheme and an EFTPOS key management system proposed by Beker, Friend and Halliden.     

A heuristic technique for multi‐agent planning

The subject of multi‐agent planning has been of continuing concern in Distributed Artificial Intelligence (DAI). In this paper, we suggest an approach to multi‐agent planning that contains heuristic elements. Our method makes use of subgoals, and derived sub‐plans, to construct a global plan. Agents solve their individual sub‐plans, which are then merged into a global plan. The suggested approach reduces overall planning time and derives a plan that approximates the optimal global plan that would have been derived by a central planner, given those original subgoals. We explore three different scenarios. The first involves a group of agents with a common goal. The second considers how agents can interleave planning and execution when planning towards a common, though dynamic, goal. The third examines the case where agents, each with their own goal, can plan together to reach a state in consensus for the group. Finally, we consider how these approaches can be adapted to handle rational, manipulative agents. This revised version was published online in June 2006 with corrections to the Cover Date.     

A fuzzy self-tuning parallel genetic algorithm for optimization

The genetic algorithm (GA) is now a very popular tool for solving optimization problems. Each operator has its special approach route to a solution. For example, a GA using crossover as its major operator arrives at solutions depending on its initial conditions. In other words, a GA with multiple operators should be more robust in global search. However, a multiple operator GA needs a large population size thus taking a huge time for evaluation. We therefore apply fuzzy reasoning to give effective operators more opportunity to search while keeping the overall population size constant. We propose a fuzzy self-tuning parallel genetic algorithm (FPGA) for optimization problems. In our test case FPGA there are four operators—crossover, mutation, sub-exchange, and sub-copy. These operators are modified using the eugenic concept under the assumption that the individuals with higher fitness values have a higher probability of breeding new better individuals. All operators are executed in each generation through parallel processing, but the populations of these operators are decided by fuzzy reasoning. The fuzzy reasoning senses the contributions of these operators, and then decides their population sizes. The contribution of each operator is defined as an accumulative increment of fitness value due to each operator's success in searching. We make the assumption that the operators that give higher contribution are more suitable for the typical optimization problem. The fuzzy reasoning is built under this concept and adjusts the population sizes in each generation. As a test case, a FPGA is applied to the optimization of the fuzzy rule set for a model reference adaptive control system. The simulation results show that the FPGA is better at finding optimal solutions than a traditional GA.     

Methodology of Concept Control Synthesis to Avoid Unmoving and Moving Obstacles (II)

Dynamic path generation problem of robot in environment with other unmoving and moving objects is considered. Generally, the problem is known in literature as find path or robot motion planning. In this paper we apply the behavioral cloning approach to design the robot controller. In behavioral cloning, the system learns from control traces of a human operator. The task for the given problem is to find a controller not only in the form of the explicit mathematical expression. So RBF neural network is used also. The goal is to apply controller for the mobile robot motion planning in situation with infinite number of obstacles. The advantage of this approach lies in the fact that a complete path can be defined off-line, without using sophisticated symbolical models of obstacles.     

Skill modeling through symbolic reconstruction of operator'strajectories

Controlling a complex dynamic system, such as a plane or a crane, usually requires a skilled operator. Such control skill is typically hard to reconstruct through introspection. Therefore an attractive approach to the reconstruction of control skill involves machine learning from operator's control traces, also known as behavioral cloning. In the most common approach to behavioral cloning, a controller is induced as a direct mapping from system states to actions. Unfortunately, such controllers usually suffer from lack of robustness and lack typical elements of human control strategies, such as subgoals and substages of the control plan. We investigate a novel approach. We apply the GoldHorn program to induce from the operator's trajectories a set of symbolic constraints. These are then used together with a locally weighted regression model to determine the next action. Using the Acrobot problem in a case study, this approach showed significant improvements both in terms of control performance and transparency of induced clones