Strong planning under partial observability

Rarely planning domains are fully observable. For this reason, the ability to deal with partial observability is one of the most important challenges in planning. In this paper, we tackle the problem of strong planning under partial observability in nondeterministic domains: find a conditional plan that will result in a successful state, regardless of multiple initial states, nondeterministic action effects, and partial observability.We make the following contributions. First, we formally define the problem of strong planning within a general framework for modeling partially observable planning domains. Second, we propose an effective planning algorithm, based on and-or search in the space of beliefs. We prove that our algorithm always terminates, and is correct and complete. In order to achieve additional effectiveness, we leverage on a symbolic, bdd-based representation for the domain, and propose several search strategies. We provide a thorough experimental evaluation of our approach, based on a wide selection of benchmarks. We compare the performance of the proposed search strategies, and identify a uniform winner that combines heuristic distance measures with mechanisms that reduce runtime uncertainty. Then, we compare our planner mbp with other state-of-the art-systems. mbp is able to outperform its competitor systems, often by orders of magnitude.     

A comparison of failure-handling approaches for planning systems—Replanning vs. recovery

A planning process formulates action assignments for various agents to accomplish a goal statement. In a real situation, unexpected environmental changes (called failures) may invalidate the preformulated plan. When a failure occurs, effective and efficient handling procedures must be taken to prevent irreversible damages. A failure-handling mechanism is a key component in a fault-tolerant system, which makes autonomous operation possible. There are two basic approaches to failure handling—replanning and recovery. In the replanning approach, the currently failure-encountered state is treated as a new initial state, and a brand-new plan is derived from scratch. On the other hand, the recovery approach preserves the applicable components of the original plan and makes necessary adjustments to the preserved plan components to fit the new state. This article presents a method of achieving recovery and compares its performance with replanning. In general, the recovery approach provides a better response time, and the replanning approach sometimes provides a better plan quality.     

An Efficient Path Planning and Control Algorithm for RUAV’s in Unknown and Cluttered Environments

This paper presents an efficient planning and execution algorithm for the navigation of an autonomous rotary wing UAV (RUAV) manoeuvering in an unknown and cluttered environment. A Rapidly-exploring Random Tree (RRT) variant is used for the generation of a collision free path and linear Model Predictive Control(MPC) is applied to follow this path. The guidance errors are mapped to the states of the linear MPC structure by using the nonlinear kinematic equations. The proposed path planning algorithm considers the run time of the planning stage explicitly and generates a continuous curvature path whenever replanning occurs. Simulation results show that the RUAV with the proposed methodology successfully achieves autonomous navigation regardless of its lack of prior information about the environment.     

Towards robust assembly with knowledge representation for the planning domain definition language (PDDL)

The effort described in this paper attempts to integrate agility aspects in the “Agility Performance of Robotic Systems” (APRS) project, developed at the National Institute of Standards and Technology (NIST). The new technical idea for the APRS project is to develop the measurement science in the form of an integrated agility framework enabling manufacturers to assess and assure the agility performance of their robot systems. This framework includes robot agility performance metrics, information models, test methods, and protocols. This paper presents models for the Planning Domain Definition Language (PDDL), used within the APRS project. PDDL is an attempt to standardize Artificial Intelligence planning languages. The described models have been fully defined in the XML Schema Definition Language (XSDL) and in the Web Ontology Language (OWL) for kit building applications. Kit building or kitting is a process that brings parts that will be used in assembly operations together in a kit and then moves the kit to the area where the parts are used in the final assembly. Furthermore, the paper discusses a tool that is capable of automatically and dynamically generating PDDL files from the models in order to generate a plan or to replan from scratch. Finally, the ability of the tool to update a PDDL problem file from a relational database for replanning to recover from failures is presented.     

Control-Based Adaptive Middleware for Real-Time Image Transmission over Bandwidth-Constrained Networks

Real-time image transmission is crucial to an emerging class of distributed embedded systems operating in open network environments. Examples include avionics mission replanning over Link-16, security systems based on wireless camera networks, and online collaboration using camera phones. Meeting image transmission deadlines is a key challenge in such systems due to unpredictable network conditions. In this paper, we present CAMRIT, a Control-based Adaptive Middleware framework for Real-time Image Transmission in distributed real-time embedded systems. CAMRIT features a distributed feedback control loop that meets image transmission deadlines by dynamically adjusting the quality of image tiles. We derive an analytic model that captures the dynamics of a distributed middleware architecture. A control-theoretic methodology is applied to systematically design a control algorithm with analytic assurance of system stability and performance, despite uncertainties in network bandwidth. Experimental results demonstrate that CAMRIT can provide robust real-time guarantees for a representative application scenario.     

Fast replanning for navigation in unknown terrain

Mobile robots often operate in domains that are only incompletely known, for example, when they have to move from given start coordinates to given goal coordinates in unknown terrain. In this case, they need to be able to replan quickly as their knowledge of the terrain changes. Stentz' Focussed Dynamic A/sup */ (D/sup */) is a heuristic search method that repeatedly determines a shortest path from the current robot coordinates to the goal coordinates while the robot moves along the path. It is able to replan faster than planning from scratch since it modifies its previous search results locally. Consequently, it has been extensively used in mobile robotics. In this article, we introduce an alternative to D/sup */ that determines the same paths and thus moves the robot in the same way but is algorithmically different. D/sup */ Lite is simple, can be rigorously analyzed, extendible in multiple ways, and is at least as efficient as D/sup */. We believe that our results will make D/sup */-like replanning methods even more popular and enable robotics researchers to adapt them to additional applications.     

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.     

Approximate performance modeling and decision making for manufacturing systems: A queueing network optimization framework

In this paper we discuss queueing network methodology as a framework to address issues that arise in the design and planning of discrete manufacturing systems. Our review focuses on three aspects: modeling of manufacturing facilities, performance evaluation and optimization with queueing networks. We describe both open and closed network models and present several examples from the literature illustrating applications of the methodology. We also provide a brief outline of outstanding research issues. The paper is directed towards the practitioner with operations research background and the operations management researcher with interest in this topic.     

Robust planning of airport platform buses

Most airports have two types of gates: gates with an air bridge to the terminal and remote stands. For flights at a remote stand, passengers are transported to and from the aircraft by platform buses. In this paper we investigate the problem of planning platform buses as it appears at Amsterdam Airport Schiphol. We focus on robust planning, i.e. we want to avoid that the bus planning is affected by flight delays and in this way invokes delays in other flights and ground-handling processes. We present a column generation algorithm for planning of platform buses that maximizes robustness. We also present a discrete-event simulation model to compare our algorithm to a first-come-first-served heuristic as is used in current practice. Our computational results with real-life data indicate that our algorithm significantly reduces the number of replanning steps and special recovery measures during the day of operation.     

Model-driven engineering of planning and optimisation algorithms for pervasive computing environments

This paper presents a model-driven approach to developing pervasive computing applications that exploits design-time information to support the engineering of planning and optimisation algorithms that reflect the presence of uncertainty, dynamism and complexity in the application domain. In particular, the task of generating code to implement planning and optimisation algorithms in pervasive computing domains is addressed.We present a layered domain model that provides a set of object-oriented specifications for modelling physical and sensor/actuator infrastructure and state-space information. Our model-driven engineering approach is implemented in two transformation algorithms. The initial transformation parses the domain model and generates a planning model for the application being developed that encodes an application’s states, actions and rewards. The second transformation parses the planning model and selects and seeds a planning or optimisation algorithm for use in the application.We present an empirical evaluation of the impact of our approach on the development effort associated with two pervasive computing applications from the Intelligent Transportation Systems (ITS) domain, and provide a quantitative evaluation of the performance of the algorithms generated by the transformations.     

A comprehensive framework for the evaluation of ontology modularization

The Semantic Web and ontologies have received increased attention in recent years. The delivery of well-designed ontologies enhances the effect of Semantic Web services, but building ontologies from scratch requires considerable time and effort. Modularizing ontologies and integrating ontology modules to a given context help users effectively develop ontologies and revitalize ontology dissemination. Therefore, various tools for modularizing ontologies have been developed. However, selecting an appropriate tool to fit a given context is difficult because the assumptions for the approaches greatly vary. Therefore, a suitable framework is required to compare and help screen the most suitable modularization tool.In this research, we propose a new evaluation framework for selecting an appropriate ontology modularization tool. We present three aspects of tool evaluation as the main dimensions for the assessment of modularization tools: tool performance, data performance, and usability.This study provides an implicit evaluation and an empirical analysis of three modularization tools. It also provides an evaluation method for ontology modularization, enabling ontology engineers to compare different modularization tools and easily choose an appropriate one for the production of qualifying ontology modules.The experimental results indicate that the proposed evaluation criteria for ontology modularization tools are valid and effective. This research provides a useful method for assessing and selecting ontology modularization tools. Modularization performance, data performance, and usability are the three modularization aspects designed and applied to the context of ontology. We provide a new focus on the comprehensive framework to evaluate the performance and usability of ontology modularization tools. The proposed framework should be of value to both ontology engineers, who are interested in ontology modularization, and to practitioners, who need information on how to evaluate and select a specific type of ontology tool in accordance with the requirements of the individual environment.     

Complexity results for standard benchmark domains in planning

The efficiency of AI planning systems is usually evaluated empirically. For the validity of conclusions drawn from such empirical data, the problem set used for evaluation is of critical importance. In planning, this problem set usually, or at least often, consists of tasks from the various planning domains used in the first two international planning competitions, hosted at the 1998 and 2000 AIPS conferences. It is thus surprising that comparatively little is known about the properties of these benchmark domains, with the exception of Blocksworld, which has been studied extensively by several research groups.In this contribution, we try to remedy this fact by providing a map of the computational complexity of non-optimal and optimal planning for the set of domains used in the competitions. We identify a common transportation theme shared by the majority of the benchmarks and use this observation to define and analyze a general transportation problem that generalizes planning in several classical domains such as Logistics, Mystery and Gripper. We then apply the results of that analysis to the actual transportation domains from the competitions. We next examine the remaining benchmarks, which do not exhibit a strong transportation feature, namely Schedule and FreeCell.Relating the results of our analysis to empirical work on the behavior of the recently very successful FF planning system, we observe that our theoretical results coincide well with data obtained from empirical investigations.     

Improved 3D Interpolation-Based Path Planning for a Fixed-Wing Unmanned Aircraft

Path planning for unmanned aircraft has attracted a remarkable amount of interest from the research community. However, planning in large environments such as the civil airspace has not been addressed extensively. In this paper we apply a heuristic incremental interpolation-based search algorithm with efficient replanning capabilities to the path planning problem for a fixed-wing aircraft operating in a natural environment to plan and re-plan long flight paths. We modified the algorithm to account for the minimum turning radius and the limited flight path angles of a fixed-wing aircraft. Additionally, we present a method to consider a desired minimum cruising altitude and a post-processing algorithm to improve the path and remove unnecessary path points. These properties specific to aircraft operation could not be addressed with the original algorithm. Simulation results show that the planner produces intuitive, short paths and is capable of exploiting previous planning efforts, when unknown obstacles are encountered.     

ON-LINE CASE-BASED PLANNING

Some domains, such as real-time strategy (RTS) games, pose several challenges to traditional planning and machine learning techniques. In this article, we present a novel on-line case-based planning architecture that addresses some of these problems. Our architecture addresses issues of plan acquisition, on-line plan execution, interleaved planning and execution, and on-line plan adaptation. We also introduce the Darmok system, which implements this architecture to play Wargus (an open source clone of the well-known RTS game Warcraft II ). We present empirical evaluation of the performance of Darmok and show that it successfully learns to play the Wargus game.     

Integrating explicit path planning with reactive control of mobile robots using Trulla

This article describes and investigates a method of interleaving explicit path planning with reactive control. The Trulla all-paths planner computes an a priori set of optimal paths. Minor reactions to obstacles and terrain changes serve to switch the robot from the precomputed path to a new precomputed path, eliminating subgoal obsession. Major deviations suggest that the a priori map is significantly wrong; explicit replanning should be triggered to ensure continued progress of the robot. The dot product is used as the intrinsic measure of a major deviation. This methodology is particularly well-suited for computationally bound robots such as planetary rovers and robots operating in indoor environments with a large number of minor unmodeled obstacles.

The article describes the Trulla and dot product algorithms, and reports on experimental data collected from a mobile robot under representative scenarios. The method is compared to continuous and fixed frequency replanning under differing environments and robot velocities. The results show that the deferred replanning with the Trulla/dot product methodology produced actual paths similar to more frequent replanning in distance and time but with up to 100 times less computation. The reduced computation led to a 8.75% increase in distance traveled and 24% increase in travel time. In the presence of faulty sensor data, Trulla outperformed the other methods which radically changed the path back and forth due to spurious sensor readings.     

Robot Motion Planning in Dynamic Uncertain Environments

In the real world, mobile robots often operate in dynamic and uncertain environments. Therefore, it is necessary to develop a motion planner capable of real-time planning that also addresses uncertainty concerns. In this paper, a new algorithm, Dynamic AO* (DAO*), is developed for navigation tasks of mobile robots. DAO* not only performs a good anytime behavior and offers a fast replanning framework, but also considers the motion uncertainty. Moreover, by incorporating DAO* with D* Lite, a new planning architecture, DDAO*, is represented to efficiently search in large state spaces. Finally, simulations and experiments are shown to verify the efficiency of the proposed algorithms.     

Ranking Learning Algorithms: Using IBL and Meta-Learning on Accuracy and Time Results

We present a meta-learning method to support selection of candidate learning algorithms. It uses a k-Nearest Neighbor algorithm to identify the datasets that are most similar to the one at hand. The distance between datasets is assessed using a relatively small set of data characteristics, which was selected to represent properties that affect algorithm performance. The performance of the candidate algorithms on those datasets is used to generate a recommendation to the user in the form of a ranking. The performance is assessed using a multicriteria evaluation measure that takes not only accuracy, but also time into account. As it is not common in Machine Learning to work with rankings, we had to identify and adapt existing statistical techniques to devise an appropriate evaluation methodology. Using that methodology, we show that the meta-learning method presented leads to significantly better rankings than the baseline ranking method. The evaluation methodology is general and can be adapted to other ranking problems. Although here we have concentrated on ranking classification algorithms, the meta-learning framework presented can provide assistance in the selection of combinations of methods or more complex problem solving strategies.     

Recovering from execution errors in SIPE

In real-world domains (e.g., a mobile robot environment), things do not always proceed as planned, so it is important to develop better execution-monitoring techniques and replanning capabilities. This paper describes these capabilities in the SIPE (System for Interactive Planning and Execution Monitoring) planning system. The motivation behind SIPE is to place enough limitations on the representation so that planning can be done efficiently, while retaining sufficient power to still be useful. This work assumes that new information given to the execution monitor is in the form of predicates, thus avoiding the difficult problem of how to generate these predicates from information provided by sensors.
The replanning module presented here takes advantage of the rich structure of SIPE plans and is intimately connected with the planner, which can be called as a subroutine. This allows the use of SIPE's capabilities to determine efficiently how unexpected events affect the plan being executed and, in many cases, to retain most of the original plan by making changes in it to avoid problems caused by these unexpected events. SIPE is also capable of shortening the original plan when serendipitous events occur. A general set of replanning actions is presented along with a general replanning capability that has been implemented by using these actions.     

A methodology for rapid illumination-invariant face recognition using image processing filters

Achieving illumination invariance in the presence of large pose changes remains one of the most challenging aspects of automatic face recognition from low resolution imagery. In this paper, we propose a novel recognition methodology for their robust and efficient matching. The framework is based on outputs of simple image processing filters that compete with unprocessed greyscale input to yield a single matching score between two individuals. Specifically, we show how the discrepancy of the illumination conditions between query input and training (gallery) data set can be estimated implicitly and used to weight the contributions of the two competing representations. The weighting parameters are representation-specific (i.e. filter-specific), but not gallery-specific. Thus, the computationally demanding, learning stage of our algorithm is offline-based and needs to be performed only once, making the added online overhead minimal. Finally, we describe an extensive empirical evaluation of the proposed method in both a video and still image-based setup performed on five databases, totalling 333 individuals, over 1660 video sequences and 650 still images, containing extreme variation in illumination, pose and head motion. On this challenging data set our algorithm consistently demonstrated a dramatic performance improvement over traditional filtering approaches. We demonstrate a reduction of 50–75% in recognition error rates, the best performing method-filter combination correctly recognizing 97% of the individuals.