Decision-theoretic planning with generalized first-order decision diagrams

Many tasks in AI require representation and manipulation of complex functions. First-Order Decision Diagrams (FODD) are a compact knowledge representation expressing functions over relational structures. They represent numerical functions that, when constrained to the Boolean range, use only existential quantification. Previous work has developed a set of operations for composition and for removing redundancies in FODDs, thus keeping them compact, and showed how to successfully employ FODDs for solving large-scale stochastic planning problems through the formalism of relational Markov decision processes (RMDP). In this paper, we introduce several new ideas enhancing the applicability of FODDs. More specifically, we first introduce Generalized FODDs (GFODD) and composition operations for them, generalizing FODDs to arbitrary quantification. Second, we develop a novel approach for reducing (G)FODDs using model checking. This yields – for the first time – a reduction that maximally reduces the diagram for the FODD case and provides a sound reduction procedure for GFODDs. Finally we show how GFODDs can be used in principle to solve RMDPs with arbitrary quantification, and develop a complete solution for the case where the reward function is specified using an arbitrary number of existential quantifiers followed by an arbitrary number of universal quantifiers.     

Formal design and verification of operational transformation algorithms for copies convergence

Distributed groupware systems provide computer support for manipulating objects such as a text document or a filesystem, shared by two or more geographically separated users. Data replication is a technology to improve performance and availability of data in distributed groupware systems. Indeed, each user has a local copy of the shared objects, upon which he may perform updates. Locally executed updates are then transmitted to the other users. This replication potentially leads, however, to divergent (i.e. different) copies. In this respect, Operational Transformation (OT) algorithms are applied for achieving convergence of all copies, i.e. all users view the same objects. Using these algorithms users can exchange their updates in any order since the convergence should be ensured in all cases. However, the design of such algorithms is a difficult and error-prone activity since building the correct updates for maintaining good convergence properties of the local copies requires examining a large number of situations. In this paper, we present the modelling and deductive verification of OT algorithms with algebraic specifications. We show in particular that many OT algorithms in the literature do not satisfy convergence properties unlike what was stated by their authors.     

An integral theorem prover and the role of proof planning

An investigation is made into the ways proof planning can enhance the capability of a rule based prover for the theory of integration. The integrals are of the Riemann type and are defined in a way to maximize the theorem proving methods of predicate calculus. Approximately fifty theorems have been proved and several examples are discussed. A major shortcoming was found to be the inability of the system to work with or produce a proof plan. As a result, a planning scheme based on the idea of subgoals or milestones was considered. With user defined plans, there was a substantial increase in performance and capability of the system and, in some cases, proofs which were previously unsuccessful were completed.     

Optimum motion planning in joint space for robots using genetic algorithms

The optimum motion planning in joint space (OMPJS) for robots, which generally consists of two subproblems, optimum path planning and optimum trajectory planning, was considered as a whole in the paper. A new method for optimum motion planning problem based on an improved genetic algorithm is proposed, which is more general, flexible and effective. This approach incorporates kinematics constraints, dynamics constraints, and control constraints of robotic manipulator. The simulation results for a two and a three degrees of freedom robots are presented and discussed. The simulations are based on genetic algorithm class library WGAClass 1.0 developed by us with Borland C++ 3.1.     

The path and location planning of workpieces by genetic algorithms

This paper presents the planning of a near-optimum path and location of a workpiece by genetic algorithms. The purpose of this planning is to minimize the processing time required for a robot to complete its work on a workpiece. The location of the workpiece can be anywhere by translating it along any direction and by rotating it about the fixedz-axis of the robot coordinate system. Owing to the changeable location of the workpiece and the alterable motion time required for a robot to move between two workpoints, the path and location planning problem is much more complicated than the travelling salesman problem. It is definitely impossible to obtain an optimum path and location within an acceptable time. In this paper, genetic algorithms are applied to solve this problem. The location of the workpiece is defined by three position parameters and one angular parameter, and the path is determined based on the values of the parameters for all workpoints. All the path and location parameters are encoded into a binary string. They are modified simultaneously by genetic algorithms to search for a global solution. As the workpiece can be anywhere, a penalty function is used to prevent the selection of illegal paths. Two experiments are given to show the performance of genetic algorithms: one has 30 workpoints and the other has 50 workpoints. Compared with four human-generated plannings, planning by genetic algorithms has much better performance in minimizing the processing time.     

A new model for path planning with interval data

In this paper, we establish a new model for path planning with interval data which arises in a variety of applications. It is formulated as minimum risk-sum path problem  : given a source-destination pair in a network G=(V,E)$G=(V,E)$, traveling on each link e in G   may take time _xe$x_e$ in a prespecified interval [_le,_ue]$[l_e,u_e]$ and take risk (_ue-_xe)/(_ue-_le)$(u_e-x_e)/(u_e-l_e)$, the goal is to find a path in G from the source to the destination, together with an allocation of travel times along each link on the path, so that the total travel time of links on the path is no more than a given time bound and the risk-sum over the links on the path is minimized. Our study shows that this new model has two features that make it different from the existing models. First, the minimum risk-sum path problem is polynomial-time solvable, and second, it provides many solutions that vary with time bounds and risk sums and leaves the choice for decision makers. Therefore, the new model is more flexible and easier to use for the path planning with interval data.     

Automated instructional design for CSCL: A hierarchical task network planning approach

In Computer Supported Collaborative Learning (CSCL), one of the most important tasks for instructional designers is to define scenarios that foster group learning. Such scenarios, defined as Units of Learning (UoLs), comprise different components and are organized according to pedagogical approaches to orchestrate group learning processes. Examples of UoL components are learning objects, student roles, student characteristics (e.g., background, preferences, learning styles, etc.), instructional/learning goals, and activities, among others. Thus, the instructional design (ID) of a proper UoL for CSCL is a complex task that requires practice and experience. This is particularly true when designing, developing, adapting, and customizing UoLs, taking into consideration different instructional/learning goals and individual preferences of students. This paper therefore proposes using a Hierarchical Task Network (HTN) planning approach to automate and optimize the tasks of designers. To accomplish that, we define an initial CSCL scenario as “an ID task” and “a set of information related to students and the domain to be taught.” Then we propose a model that formally describes ID for CSCL as HTN planning, where the initial CSCL scenario is adapted and refined according to student needs. In this model, the ID strategies are defined as hierarchical tasks and methods into a planning domain definition, and the initial CSCL scenario is defined as a planning problem definition. To validate our approach, we develop a CSCL courseware generator that (i) helps designers to set up an initial CSCL scenario; (ii) automatically generates a personalized UoL based on a given initial scenario; and (iii) supports the adaptation of UoLs.     

Genetic algorithms in integrated process planning and scheduling

Process planning and scheduling are actually interrelated and should be solved simultaneously. Most integrated process planning and scheduling methods only consider the time aspects of the alternative machines when constructing schedules. The initial part of this paper describes a genetic algorithm (GA) based algorithm that only considers the time aspect of the alternative machines. The scope of consideration is then further extended to include the processing capabilities of alternative machines, with different tolerance limits and processing costs. In the proposed method based on GAs, the processing capabilities of the machines, including processing costs as well as number of rejects produced in alternative machine are considered simultaneously with the scheduling of jobs. The formulation is based on multi-objective weighted-sums optimization, which are to minimize makespan, to minimize total rejects produced and to minimize the total cost of production. A comparison is done w ith the traditional sequential method and the multi-objective genetic algorithm (MOGA) approach, based on the Pareto optimal concept.     

Experimental validation and comparative analysis of optimal time-jerk algorithms for trajectory planning

In this paper, two minimum time-jerk trajectory planning algorithms for robotic manipulators have been considered, evaluated and experimentally validated. These algorithms consider both the execution time and the integral of the squared jerk along the whole trajectory, so as to take into account the need for fast execution and the need for a smooth trajectory, by adjusting the values of two weights. A comparative analysis of these algorithms with two different trajectory planning techniques taken from the literature has been carried out, by means of experimental tests performed on a real robotic manipulator. The results prove the experimental effectiveness of the proposed techniques.     

A symbolic framework for multi-faceted security protocol analysis

Verification of software systems, and security protocol analysis as a particular case, requires frameworks that are expressive, so as to properly capture the relevant aspects of the system and its properties, formal, so as to be provably correct, and with a computational counterpart, so as to support the (semi-) automated certification of properties. Additionally, security protocols also present hidden assumptions about the context, specific subtleties due to the nature of the problem and sources of complexity that tend to make verification incomplete. We introduce a verification framework that is expressive enough to capture a few relevant aspects of the problem, like symmetric and asymmetric cryptography and multi-session analysis, and to make assumptions explicit, e.g., the hypotheses about the initial sharing of secret keys among honest (and malicious) participants. It features a clear separation between the modeling of the protocol functioning and the properties it is expected to enforce, the former in terms of a calculus, the latter in terms of a logic. This framework is grounded on a formal theory that allows us to prove the correctness of the verification carried out within the fully fledged model. It overcomes incompleteness by performing the analysis at a symbolic level of abstraction, which, moreover, transforms into executable verification tools.     

动态未知环境下一种新的机器人路径规划方法

针对机器人动态路径规划问题,提出了一种机器人在复杂动态环境中实时路径规划方法.该方法基于滚动窗口的路径规划和避障策略,通过设定可视点子目标、绕行障碍物和对动态障碍物的分析预测,实现机器人在复杂动态环境下的路径规划.针对障碍物分布情况,合理设计可视点法和绕行算法之间转换,有效地解决了局部路径规划的死循环与极小值问题.该方...     

Hybrid ant colony algorithms for path planning in sparse graphs

The general problem of path planning can be modeled as a traveling salesman problem which assumes that a graph is fully connected. Such a scenario of full connectivity is however not always realistic. One such motivating example for us is the application of path planning for unmanned reconnaissance aerial vehicles (URAVs). URAVs are widely deployed for photography or imagery gathering missions of sites of interest. These sites can be targets in a combat zone to be investigated or sites inaccessible by ground transportation, such as those hit by forest fires, earthquake or other forms of natural disasters. The navigation environment is one where the overall configuration of the problem is a sparse graph. Unlike graphs that are fully connected, sparse graphs are not always Hamiltonian. In this paper, we describe hybrid ant colony algorithms (HACAs) proposed for path planning in sparse graphs since existing ant colony solvers designed for solving TSP do not apply to the present context directly. HACAs represent ant inspired algorithms incorporated with a local search procedure and some heuristic techniques for uncovering feasible route(s) or path(s) in a sparse graph within tractable time. Empirical results conducted on a set of generated sparse graphs demonstrate the excellent convergence property and robustness of HACAs in uncovering low risk and Hamiltonian visitation paths. Further, the obtained results also indicate that HACAs converge to secondary closed paths in situations where a Hamiltonian cycle does not exist theoretically or is not attainable within the bounded computational time window.     

基于RBR和CBR规划中的知识表示方法研究

知识是规划的前提和基础,通过归纳对已有知识的表示,就成为了规划的先行条件.基于规则和案例的规划是各种现代规划器常用的两种规划方式,通过对现有的规则和案例的各种知识表示方法的研究,描述了其各自的优缺点,并给出了如何选择合适的知识表示方法以处理特定规划问题的方法和思想,从而更快,更好的构建能够解决实际问题的规划系统.     

Proof systems for planning under O-approximation semantics

In this paper we propose Hoare style proof systems called PRD^0and PRKWD^0 for plan generation and plan verification under 0-approximation semantics of the action language AK.In PRD^0 （resp.PRKW0D）,a Hoare triple of the form{X}c{Y}（resp.{X}c{KWp}）means that all literals in Y become true（resp.p becomes known）after executing plan c in a state satisfying all literals in X.The proof systems are shown to be sound and complete,and more importantly,they give a way to efficiently generate and verify longer plans from existing verified shorter plans by applying so-called composition rule,provided that an enough number of shorter plans have been properly stored.The idea behind is a tradeoff between space and time,we refer it to off-line planning and point out that it could be applied to general planning problems.     

A survey on coverage path planning for robotics

Coverage Path Planning (CPP) is the task of determining a path that passes over all points of an area or volume of interest while avoiding obstacles. This task is integral to many robotic applications, such as vacuum cleaning robots, painter robots, autonomous underwater vehicles creating image mosaics, demining robots, lawn mowers, automated harvesters, window cleaners and inspection of complex structures, just to name a few. A considerable body of research has addressed the CPP problem. However, no updated surveys on CPP reflecting recent advances in the field have been presented in the past ten years. In this paper, we present a review of the most successful CPP methods, focusing on the achievements made in the past decade. Furthermore, we discuss reported field applications of the described CPP methods. This work aims to become a starting point for researchers who are initiating their endeavors in CPP. Likewise, this work aims to present a comprehensive review of the recent breakthroughs in the field, providing links to the most interesting and successful works.     

Assumptive planning and execution: A simple, working robot architecture

In this paper, we present a simple approach to interleaving planning and execution based on the idea of making simplifying assumptions. Since assumptions can be tragically wrong, this assumptive approach must ensure both that the robot does not believe it has solved a problem when it has not and that it does not take steps that make a problem unsolvable. We present an assumptive algorithm that preserves goal-reachability and in addition we specify conditions under which the assumptive architecture is sound and complete.We have successfully implemented the assumptive architecture on several real-world robots. Students in an introductory robot lab at Stanford University implement an assumptive system on robots that have incomplete information about their maze world. Dervish, our winning entry in the 1994 AAAI National Robot Competition, implements an assumptive architecture to cope with partially specified environments and unreliable effectors and sensors.     

A generalized model for financial time series representation and prediction

Traditional financial analysis systems utilize low-level price data as their analytical basis. For example, a decision-making system for stock predictions regards raw price data as the training set for classifications or rule inductions. However, the financial market is a complex and dynamic system with noisy, non-stationary and chaotic data series. Raw price data are too random to characterize determinants in the market, preventing us from reliable predictions. On the other hand, high-level representation models which represent data on the basis of human knowledge of the problem domain can reduce the randomness in the raw data. In this paper, we present a high-level representation model easy to translate from low-level data into the machine representation. It is a generalized model in that it can accommodate multiple financial analytical techniques and intelligent trading systems. To demonstrate this, we further combine the representation with a probabilistic model for automatic stock trades and provide promising results. An erratum to this article can be found at     

Proof systems for planning under 0-approximation semantics

In this paper we propose Hoare style proof systems called PR0Dand PRKW0Dfor plan generation and plan verification under 0-approximation semantics of the action language AK.In PR0D(resp.PRKW0D),a Hoare triple of the form{X}c{Y}(resp.{X}c{KWp})means that all literals in Y become true(resp.p becomes known)after executing plan c in a state satisfying all literals in X.The proof systems are shown to be sound and complete,and more importantly,they give a way to efficiently generate and verify longer plans from existing verified shorter plans by applying so-called composition rule,provided that an enough number of shorter plans have been properly stored.The idea behind is a tradeoff between space and time,we refer it to off-line planning and point out that it could be applied to general planning problems.     

A logic-based agent that plans for extended reachability goals

Planning to reach a goal is an essential capability for rational agents. In general, a goal specifies a condition to be achieved at the end of the plan execution. In this article, we introduce nondeterministic planning for extended reachability goals (i.e., goals that also specify a condition to be preserved during the plan execution). We show that, when this kind of goal is considered, the temporal logic ctl turns out to be inadequate to formalize plan synthesis and plan validation algorithms. This is mainly due to the fact that the ctl’s semantics cannot discern among the various actions that produce state transitions. To overcome this limitation, we propose a new temporal logic called α-ctl. Then, based on this new logic, we implement a planner capable of synthesizing reliable plans for extended reachability goals, as a side effect of model checking.