CENIIT project 06.09: Robust Planning Systems for Aerospace Applications

This project is funded by CENIIT, the Center for Industrial Information Technology.

Table of contents:

• Background and Industrial Motivation

• Original Vision and Goals

• Research Environment and Industrial Cooperation

• Researchers

• Project Results

• Project Publications

• References

• Previous Publications

1. Background and Industrial Motivation

Planning is the art of thinking before you act, determining a course of action that is likely to achieve your goals without adverse consequences. Planning can be done by humans, but also by autonomous systems that are given formally defined goals to be achieved in the environment in which they operate.

In some cases, a system can succeed in achieving its goals without planning, using reactive behaviours where goal direction has been built in implicitly by a human designer. However, autonomous systems are now expected to handle increasingly intricate tasks in increasingly complex environments, performing tasks such as monitoring and controlling complicated industrial processes, surveillance and information gathering using unmanned aerial vehicles (UAVs), or the exploration of the outer reaches of the solar system using partly or completely autonomous spacecraft. As the complexity of a task increases, so does the difficulty of defining reactive behaviours that are guaranteed to cover all potential contingencies. In such cases, it is often preferable to be able to reason at a higher level about an explicit model of the world, using planning techniques to find a suitable course of action. Consequently, planning has been an active field of research for several decades.

The existence of an explicit model of the world also allows a planner to predict what would happen if a given plan were to be executed. This is useful during plan generation, because it permits the user to specify explicit safety conditions that must not be violated. Due to the system's ability to predict the consequences of its actions, such safety conditions can be tested even before the plan is executed. By anticipating not only the outcome of a single action but the outcome of a complete plan, a planner can ensure that actions that may lead to failure are not performed, even when the negative consequences of such actions are not immediate. The use of an explicit model is also of use during plan execution, when one may monitor the actual effects of the actions being performed and compare this to the predictions made by the planner, halting the execution and replanning if any discrepancies are detected. Furthermore, the existence of an explicit plan can be an invaluable aid to the user of an autonomous system, because it enables the system to inform the user of its intended actions before they take place and provides a motivation for those actions.

This, of course, requires the development of formal planning methods that are able to handle the full complexity of the environment in which the system will act. Historically, planning methods have been severely limited in terms of speed as well as expressivity, usually requiring complete and correct information about all aspects of the environment and the effects of the actions at their disposal while still not being efficient enough to handle problems of a reasonable size. In the last several years, our understanding of the planning problem has improved, and planners have made great strides both in expressivity and in speed. However, there is still a great deal of work to be done before planners are expressive enough to capture the intricacies of many real world planning domains and robust enough to handle all types of contingencies that may occur in complex operating environments. A successful treatment of these problems can be expected to yield enormous benefits, both due to the fact that new application areas for autonomous systems will open up and due to an increase in robustness for existing autonomous systems.

Within this project, we work with automated planning in complex domains such as the autonomous UAV (unmanned aerial vehicle) domain. An important guiding principle throughout the project has been to continually close the loop between theory and practice by implementing, integrating and evaluating potential solutions in real-world usage. In most cases, this entails integrating our solutions in the UASTech UAV architecture developed at the AIICS division and testing implemented prototypes and systems in hardware-in-the-loop simulation as well as in test flights in Motala and in Revinge. This is essential in order to demonstrate the viability of our solutions to our industrial partners in preparation for future integration into their products. As one example, Saab Aerosystems has shown great interest in integrating our planner TALplanner into their Skeldar UAV.

2. Original Vision and Goals

This section describes the original visions and goals as presented in the initial project plan, including the definition of four specific research areas. As will be seen in the progress report, our research has mainly taken place in three of these areas, and starting in 2009, we explicitly focus on two specific areas.

Our research aims towards increasing the applicability of automated planning techniques for autonomous systems operating in complex environments.

We can identify two separate but equally necessary aspects of this high-level goal: Planning techniques must become more expressive, in order to be able to robustly model a greater variety of domains that cannot be described at a sufficient degree of accuracy using current planners, and they must become more efficient, which requires the development of new techniques for handling the required extensions to expressivity within the time and resource requirements placed upon the relevant autonomous systems. These requirements might appear to be contradictory, and some tradeoffs will likely have to be made, but research during the last few years has shown that there is still space for considerable simultaneous improvements in both areas.

We intend most of our research to take place within four concrete subprojects: Planning with incomplete information, integration of motion planning with task planning, integration of planning with execution monitoring, and mixed initiative planning. Before describing these subprojects, we will first provide a very brief introduction to TALplanner, one of the planners that we have developed in the last several years and that will form the basis for future planning research.

TALplanner

Many new planners and algorithms have contributed to moving the research frontier forward in recent years. One of them, TALplanner [r9,r10,r14,r15,r17,r18,r19], was developed by our research group and won several prizes in the AIPS-2000 international planning competition [r10], often beating the competition in the hand-tailored track by orders of magnitude.

The hand-tailored track of the competition was reserved for planners that can accept not only the most basic description of a planning problem but also additional domain information that may help guide the planning algorithm towards finding a valid plan. In TALplanner, which is a hand-tailored or knowledge-rich planner, such information usually takes the shape of general rules describing courses of action that are not fruitful, such as (in a transportation domain) unloading a package before it has reached its destination. It should be noted that this is not low-level information that directly controls the algorithmic behaviour of the planner; instead, it takes the shape of high-level declarative knowledge directly related to the domain for which plans are being related. We view the ability to accept and make use of such information as a necessity if one expects to produce general purpose planners that can generate high quality plans in complex environments with sufficient speed.

Planning with incomplete information

Classical planning algorithms are based on the fundamental assumption of complete knowledge about the initial state of the world, where a plan will eventually be executed, as well as about all effects of the actions that are available during plan execution. This is reasonable in some domains, but the applicability of a planner can be extended manyfold by relaxing this assumption and allowing partially specified states and operators. In a UAV domain, for example, one would generally expect to be able to work with a partial map of the environment, adding information to this map as the UAV investigates a given area. However, this requires significant changes to planning algorithms as well as to the structure of the plans being generated; for example, one generally has to introduce sensing actions together with conditional plans where different branches are taken depending on what is sensed in the environment.

Though planning with incomplete information is certainly not a new problem, we believe we are in a very strong position to take this research another step forward, for the following reasons.

First, although relaxing the assumption of complete knowledge about action effects and the initial state certainly makes plan generation more difficult and time consuming, we expect to be able to counteract many of these these problems using techniques from knowledge-rich planning, where we already have considerable experience. This combined approach, which leads to the conceptually attractive position of being able to state all the information one has regarding a domain while not being forced to specify information one does not have, has not yet been adequately explored by the research community.

Second, while any planner must be able to represent and reason about the information provided regarding its operating environment, the required data structures and reasoning mechanisms are considerably more complex in the case of incomplete information. The desire to keep such mechanisms tractable often leads to limitations in the types of queries that can be answered as well as to querying techniques that are sound but not complete, in the sense that all answers are correct but not all queries can be answered. Researchers at AIICS have recently developed new methods for reasoning about incomplete information [r3,r4,r5], subsuming and greatly expanding upon existing techniques used in certain planners.

Integration of path planning and task planning

Planning domains that involve moving between locations on a map have often been treated in a highly abstract manner. In the standard logistics benchmark domain, for example, it is assumed that trucks move between any two locations in a city in a single time step; a plan is considered to be optimal if it involves the least number of ”moves”. Modern task planners do allow distances and road maps to be modeled, which is a step in the right direction. However, such models still do not capture all constraints that are placed on the paths that certain types of vehicles are able to travel. For example, a helicopter can only make a sharp ninety-degree turn while hovering in a fixed location, and an airplane cannot make such turns at all, which must be taken into consideration both when determining how much time is required to travel a certain path and when determining whether the path can be travelled at all. Such conditions are generally taken into account (at varying degrees of accuracy) by path planners, which on the other hand are limited to finding paths and therefore cannot replace task planners.

Members of this research group have previously implemented both task planners and path planners. The integration of such planners into a single coherent task and path planner is a highly relevant topic which we intend to pursue in this project. This integration will be particularly interesting in the context of knowledge-rich planning, where we intend to perform a thorough investigation of how various forms of domain knowledge can be utilized to improve the performance of a combined task and path planner.

Integration of planning and execution monitoring

In theory, plan generation is often treated as being completely separate from plan execution: First a complete plan is generated, and then it is passed in its entirety to an execution mechanism. In practice, there are many opportunities for failure during plan execution, and it is impossible to take all potential contingencies into account within the plan itself – it is always possible to find one more potential condition under which the plan would fail, however unlikely that condition may be. In any realistic application, the execution mechanism must continuously monitor the execution of the plan and react appropriately to any discrepancies compared to the results that were predicted by the planner.

In case a failure is detected by the execution monitor, the system must in some way recover from this failure, for example by finding a new plan beginning in the current, unexpected state. The execution monitoring and recovery procedure can benefit greatly from being integrated with the planner itself: The planner could automatically generate conditions to be monitored, and provide hints as to how a plan should be modified given certain types of failures. The more domain knowledge a planner has, the stronger conditions it can generate, making this research topic especially relevant when combined with the use of knowledge-rich planning. We expect this project to lead to more efficient replanning techniques as well as earlier failure detection.

Mixed Initiative Planning

Automated planning is generally viewed as a batch process, where the first stage involves collecting all available information regarding the problem to be solved and the second stage consists of executing a planning algorithm, which runs until it has generated a suitable plan. Only a small subfield of the planning area deals with mixed initiative planning, where the user continuously interacts with the planning system during plan generation. Allowing such interaction opens up an entire spectrum of possibilities, ranging from planners that still have the overall responsibility for plan generation, but allow users to guide it and dictate certain key decisions, to planners that act as decision support systems for a human planner. Once again, the combination with knowledge-rich planning leads to new and interesting aspects of mixed initiative planning, given the interaction between the more general domain knowledge provided in a domain specification and the more specific guidance that can be provided by humans in an interactive planning process.

3. Research Environment and Industrial Cooperation

This project takes place within the Artificial Intelligence and Integrated Computer Systems (AIICS) division of IDA. The division has a long history of research within the field of artificial intelligence. More specifically, we have been actively involved in the field of planning since 1998, with one of our planners, TALplanner, winning multiple awards in international planning competitions.

A planning research group has existed informally within AIICS for several years. In 2008 this arrangement has been formalized through the formation of an official group, the Automated Planning and Diagnosis group led by Jonas Kvarnström, with the specific industrial goal of developing deployable automated planning and diagnosing technologies. At the moment, four students are also part of this group: Martin Magnusson, Fredrik Heintz, Per-Magnus Olsson and Håkan Warnquist. Though Patrick Doherty is still necessarily their primary advisor, Jonas Kvarnström has taken over much of the work in guiding research within the planning area and advising several Ph.D. students. We are currently in the process of making a major update to the AIICS web pages and the new group will be reflected in this update. The intention is for this group to incrementally expand and become an independent lab in the future, with Jonas Kvarnström as lab leader.

The AIICS division also has a very strong background in automated reasoning with incomplete information, an essential issue when generating plans in an incompletely specified environment. The formalisms and algorithms that have been developed provide a strong basis for planning, and the project is pursued in close cooperation with the AIICS automated reasoning group in order to further extend the relevant mechanisms.

Research in the field of planning is all too often only validated using artificially constructed benchmark tests. Such benchmarks can be quite useful in some respects, and is part of our testing procedures. More importantly, our research is also integrated into a long term unmanned aerial vehicle (UAV) project at the UAV Technologies Lab (UAVTech) at AIICS [r1,r2], which includes opportunities for both task planning and path planning, for missions involving a single UAV as well as missions for multiple cooperating UAVs. This grounds our research in real world requirements.

The UAVTech group is one of the internationally leading UAV groups in academia and at the front line of research involving autonomous technologies for UAVs. Several platforms have been developed, deployed and used in complex mission scenarios. In September 2005, the UAVTech group won first place for rotor-based micro air vehicles (MAVs) at the first US-European MAV competition in Garmisch-Partenkirchen. This is a high-profile group with a successful track record in this area in terms of basic and applied research and deployed UAV prototypes.

Through the overall UAV project, we have cooperated with Saab Aerosystems in forums such as LinkLab, a center for future aviation systems which is based on direct project and other collaboration between Saab and LiU, as well as in specific research projects, including two NFFP projects. Results have been reported through both technical reports and peer-reviewed publications, and demonstrated and discussed at several joint workshops and live demonstrations. We also have frequent industrial feedback through Patrick Doherty, who has met Jonas Palm (Saab) montly to discuss progress within the two NFFP projects and meets Gunnar Holmberg (Saab) montly to discuss progress within LinkLab. UAV data is provided to Saab groups, and a number of master's theses at Saab have been co-advised by us, providing another channel for feedback.

Saab has been very pleased with the results of this cooperation and consider it strategically important that we continue cooperation in the future. A proposal has also been submitted to SSF to develop a joint UAV lab with Saab and share platforms for future research and knowledge exchange. The intention is for TALplanner to play a central role.

We are also cooperating closely with Scania AB, who are financing Håkan Warnquist (industridoktorand) to work on the use of planning for diagnosis and troubleshooting of heavy trucks, an interesting form of planning with incomplete information. Håkan works 60% in Södertälje and 40% in Linköping, with Patrick Doherty as main advisor and Jonas Kvarnström as active co-advisor taking care of most of the advisory duties. This provides an excellent connection to another important industrial partner interested in the use of planning technologies. Mattias Nyberg at Scania is our primary contact person, but we also receive frequent feedback directly through Håkan's work in Södertälje as well as through regular "styrgruppsmöten" where several Scania representatives are present.

Other CENIIT projects. At the time of the original proposal, this project was not directly related to any of the existing CENIIT projects. There were some connections between the execution monitoring subproject and CENIIT 04.14 ”Model-based diagnosis of technical systems” in the sense that both projects involve fault detection given a model of a process or domain. However, these systems operate at significantly different levels of abstraction.

In later projects, we see a connection to CENIIT 08.01, Automated Planning and Optimization of Broadband Radio Access Networks, which also involves a form of planning. However, CENIIT 08.01 aims at a considerably more specific goal of dimensioning, configuring and reconfiguring radio networks, rather than at the general automated planning problem as defined in artificial intelligence. While we also have an interest in finding highly efficient solutions to more specific problems such as path finding, we generally prefer to be able to integrate such solutions into general planners, thereby improving performance while retaining the full applicability of the planner. The particular problem tackled by CENIIT 08.01 appears too specific to occur as a subproblem of a wide variety of general planning problems.

Fredrik Heintz, who used to participate in this CENIIT project, has now received his Ph.D. degree and has his own Ph.D. project (CENIIT 10.04: Stream-Based Reasoning Grounded Through Sensing). Our work remains closely related in the sense that reasoning about information gathered through sensing is an essential basis for the successful application of planning, and we continue to cooperate regularly within the intersection of our respective areas of interest.

Researchers

At the moment, four researchers are involved in this CENIIT project:

Jonas Kvarnström is the project leader.

Per-Magnus Olsson is a PhD student partially funded by CENIIT.

Mikael Nilsson is a PhD student partially funded by CENIIT.

Håkan Warnquist is a PhD student working within this CENIIT project but funded by Scania.

Previous researchers within the project:

Per Nyblom has finished his licentiate degree and has left the university.

Fredrik Heintz has finished his Ph.D. degree.

Martin Magnusson is finishing his Ph.D. thesis and is no longer actively working within the areas covered by this CENIIT project.

Project Results

The majority of the research performed within this project has taken place within two of the four subprojects specified in the original project proposal. In late 2008, this tighter focus was formalized through a new project plan involving the subprojects planning with incomplete information and integrating planning with execution monitoring and diagnosis. Note that the name of the latter subproject has changed slightly in order to explicitly take account of the need for diagnosis when a problem in plan execution has been detected.

Project Progress in 2006–2008: Planning with Incomplete Information

Though most planners require complete information about the environment, working with incomplete information is essential when planning for any realistic robotic domain.

In one branch of this project, leading to a licentiate thesis by Per Nyblom [10], we have explored a probabilistic approach by specifying and implementing a planner based on Dynamic Decision Networks, a relative of MDPs and POMDPs, that can be used to specify stochastic and partially observable planning models. This approach also involves the use of particle filtering techniques for the representation of probability distributions for uncertain properties such as the locations of vehicles, both during planning and during execution [4]

To deal with the complexity of these models in a principled manner, the DARE method was developed. DARE is a framework allowing a system to dynamically create abstractions of its environment, weighing level of detail against planning time to determine what level of abstraction to use for the tasks at hand. Plans are incrementally refined to lower levels of abstraction if this is necessary for execution or if an abstraction monitor detects that the assumptions on which the current decisions are based no longer hold. A prototype implementation is available and has been successfully applied to two case studies where a UAV classifies moving targets while avoiding moving and stationary dangers [1,4,10], a highly relevant topic for Saab Aerosystems.

In a parallel branch focusing on logic-based techniques, leading to a licentiate thesis by Martin Magnusson [5], we have aimed at increasing the flexibility of traditional plan structures, allowing the plan execution system greater freedom in scheduling actions depending on information gained during execution. The PARADOCS system [2,3,5] provides both prediction and planning capabilities. It generates plans where actions are linked by the relations of the Allen interval algebra, providing strictly more expressivity than the more common partial order structure. For example, a plan may state that action A can be executed before or after B, but that the actions must not overlap. Work in this area also includes an extension of Temporal Action Logic (TAL) [6] providing a formal semantics for composite actions, including loops and conditionals, in preparation for generating plans including such actions. PARADOCS has been integrated with our hardware-in-the-loop UAV simulation system and applied to an emergency service rescue UAV domain. It also provides a mixed initiative interface for goal specification, plan visualization, and choice among alternative plans.

Research initiated in PARADOCS continues in the ANDI system, which generalizes this approach in several ways [7,11,17,18]. Through additional extensions to Temporal Action Logic, it allows an agent to model incomplete knowledge about its environment and to explicitly reason about the knowledge it has as well as the knowledge of other agents. Sensing actions and other forms of knowledge-producing actions are supported, which is highly relevant for UAV applications. Through the use of speech acts, an agent using ANDI can also ask, and plan to ask, other agents – or a human operator in a mixed initiative setting – for information it requires. The framework supports conformant plans and we have also experimented with the generation of conditional plans. The generation of infinite or indefinite loops is a recent extension that has been applied to a multiple-target UAV surveillance mission [17], again a very important topic for the industrial use of UAVs.

Project Progress in 2009–2010: Planning with Incomplete Information

Uncontrollable durations.

In 2009, we developed a new planner using a novel hybrid of partial-order planning and forward-chaining planning to generate plans with both controllable and uncontrollable durations. The planner uses domain structure together with control information inspired by TALplanner for improved performance in a multi-agent setting. An initial prototype was implemented and showed promising results in an application to the multi-UAV domain.

In 2010, this planner has been extended in terms of expressivity and new methods for efficiently searching for applicable actions in the new search space have been developed. The resulting planner has been presented in two publications [37,41]. We have also begun investigations into extending this framework for planning with delegation, where the identity, number and capabilities of agents that will be available for plan execution are not known in advance [35]. In this situation, negotiation among UAVs and other entities is necessary during the planning phase, leading to new and very interesting research issues that are highly relevant to the industrial use of cooperative robotics. A proper treatment of uncontrollable durations is one important prerequisite. Our research in this area builds on the new hybrid planning framework mentioned above, as well as our earlier work in planning for communication and speech acts [27,22], which provides a fundamental basis for integrating negotiation and delegation into the planning process.

Information gathering. Though we can never expect to have complete information about the environment, we must nevertheless do our best to gather the information we can, at the highest quality possible. One aspect of this is the necessity to always anchor the symbolic information that most planners work with in incomplete and noisy sensory information originating in the real world, which requires constant validation and updates of hypotheses.

In 2009, we published a journal article with an in-depth description of DyKnow [34], which is used for this purpose in our system architecture, and developed a framework for hierarchical anchoring [31]. This work was done in cooperation with Fredrik Heintz, who presented his PhD thesis in 2009 [21] and no longer participates in this CENIIT project.

Relaying information through UAVs. Suppose several UAVs are given the joint mission of keeping a number of moving targets in sight at all times, and communicating information about the targets back to a ground station. The movement of the targets may not be known in advance. Also, there may be obstacles to direct communication between a UAV and the ground station, and one may need to relay information through other UAVs. This leads to a very interesting planning problem with incomplete information (highly interesting to Saab Aerosystems), where one must determine where each UAV should be at any moment in time in order to maximize the probability of being able to see all targets and have an unbroken chain of communication. Per-Magnus Olsson works on this problem in cooperation with Jonas Kvarnström, Oleg Burdakov (MAI) and Kaj Holmberg (MAI).

In late 2008 and 2009, we developed two new algorithms generating a set of Pareto-optimal solutions for a single static target [29,25]. These algorithms were implemented and integrated into the UASTech UAV system, where a ground operator can point and click to designate targets, after which suitable relay configurations are presented and can be delegated to a set of available UAVs.

In late 2009, we wrote an article on this work for the Journal of Global Optimization [33] and were also invited to write an extended journal article for the International Journal of Robotics Research. The latter article concludes our research into single target surveillance [38].

We also developed and implemented heuristic algorithms generating relay trees for multiple static targets. The initial plan for 2010 was then to shift our focus towards dealing with the full problem of surveilling moving targets. However, new ideas instead led to the development of a new algorithm for generating Pareto-optimal solutions for two targets, which can in turn be used in a new anytime algorithm for gradually optimizing existing relay trees generated by the heuristic algorithms mentioned above [40]. Per-Magnus' licentiate thesis is now in its final draft stage and on track to be finished before the end of September.

Project Progress in 2006–2008: Task and Path Planning

Planning for robotic systems usually requires taking motion constraints into account. In the planning phase, though, a full path plan is less important than a cost estimate allowing the planner to find an inexpensive plan in terms of cost and distance travelled and determine that this plan is likely to be executable given available resources. TALplanner has therefore been extended with a framework for pluggable cost estimators and with a heuristic optimizing search method [9]. Estimators can be vehicle-specific, adapted to the particular requirements of our Yamaha RMAX helicopters, the Saab Skeldar UAV, and so on. Two concrete estimators are implemented, one using a rough but extremely fast estimation function and one calling a probabilistic road map path planner and estimating the cost of the generated path. The architecture is fully implemented [32] and has been tested in simulation and live flight, including demonstrations for Saab Aerosystems at a number of occasions.

Recently, Mariusz Wzorek has implemented a new cost estimator based on machine learning. Experimentation shows very positive results, where estimates can be calculated on-line at a fraction of the cost associated with full path planning [36].

A combination of path and task planning is also used in the probabilistic approach mentioned above [4]. This approach uses a limited-depth lookahead to determine which course of action is likely to provide the highest net reward given the current belief state. Paths are generated to a number of points that are expected to provide rewards (achieve subgoals or minimize risk). Which path is chosen depends on the combined expected reward achievable in several execution steps as well the combined expected cost of travelling each path. After the first step in the plan is executed, the agent observes its environment, updates probabilities, and uses the newly obtained information to generate a new plan which may or may not coincide with the previous one.

Project Progress in 2006–2009: Execution Monitoring

Regardless of the care taken to model a domain and to generate flexible and adaptive plans, there will still be occasional problems during execution due to sensor or actuator failure, interference by other agents, or mistaken beliefs about the environment. Any robust plan execution system must take this into account and detect and recover from failures during execution, something which is often ignored in planning architectures. While one can to some extent handle these issues in the implementation of low level actions, there are significant benefits to having a separate execution monitoring system, not least because one often needs to monitor conditions that span multiple actions.

PARADOCS and ANDI use plan structures that are automatically annotated with certain requirements that must be satisfied for the plan to succeed [5]. An execution monitor continually tests these requirements during execution, thereby detecting a large class of failures. Additionally, the systems are built to support plan repair, where an existing plan can be dynamically extended to take a failure into account. The ability to repair a plan with minimal changes also minimizes the work required for a human operator to approve the new plan, which is very important for future UAV usage in inhabited areas due to safety regulations.

Another approach is taken in TALplanner, where monitor formulas in a powerful temporal logic are used to succinctly express complex conditions that should be monitored during execution [16,32,8]. Such formulas can be specified explicitly: Global monitors verify conditions that must hold during the entire execution of a plan, while operator-specific monitors are triggered by the execution of a specific parameterized operator, providing an important form of context-dependence. Note that these formulas are not simple state constraints but can express complex temporal conditions with delays, timeouts and interdependencies between states. An automated domain analysis system has also been developed, with the ability to automatically extract several interesting forms of monitors from a planning domain. Introspective capabilities have been added to the execution architecture, allowing formulas to refer explicitly to what is intended to happen as well as what is in fact happening in the world. The logic used is an extension to Temporal Action Logic that can be evaluated very efficiently in an incremental manner using either formula progression techniques or a compilation into finite state machines. The use of TAL also ensures a common formal semantics for both planning and monitoring.

Execution monitoring requires timely updates regarding the current state of the world. We have therefore cooperated with Fredrik Heintz, who joined this CENIIT project in 2008, in extending the DyKnow knowledge processing middleware framework, which is used to achieve situation awareness in the UASTech UAV architecture [13,19]. A state synchronization mechanism handles issues related to generating coherent high-level states from information originating in distributed and unsynchronized sensors. A formula progression component has also been added. Empirical results show that progression is highly efficient, allowing a large number of complex formulas to be evaluated in real time on our on-board UAV computer [15,32]

Having detected a problem, the system must recover. Given sufficiently specific monitor formulas, information about which formula has been violated provides an initial indication of the type of failure. Each formula can also be associated with a recovery action, providing a context-dependent means for recovery. For example, one may perform an emergency break, retry the current action, adjust current assumptions about the environment, repair or redo the current plan, and/or ask for instructions from a human operator in a mixed initiative setting.

The combined planning and execution monitoring system is fully implemented and integrated into our robotic architecture. It has been tested in flight as well as in simulation with extensive use of failure injection. Execution monitoring is highly relevant to our industrial partners and the complete system has been demonstrated to a Saab Aerosystems delegation in live flight tests.

Finally, we are also very interested in other forms of on-line and off-line diagnosis, which is strongly related to execution monitoring. Cooperation with ISY in this area has led to the FlexDx system, which is based on the use of DyKnow [15,20].

Project Progress in 2009–2010: Execution Monitoring and Diagnosis

Diagnosis through probabilistic planning. Consider the problem of off-line diagnosis and repair of a complex vehicular system such as a heavy truck or a UAV. A mechanic can test and observe various parts of the vehicle and repair or replace components. The cost for doing so depends on the degree to which the vehicle has been disassembled. While some tests directly determine whether a specific component is malfunctioning, others merely provide information that has to be used in conjunction with a probabilistic model of potential faults and their directly observable effects. What test and repair actions should be performed in order to guarantee, with minimal cost, that the vehicle is fully functioning? This problem can be attacked using probabilistic planning techniques, placing it right in the intersection of our two focus areas.

In 2008 and 2009, a prototype troubleshooter for a retarder (truck braking system) was developed, using a form of probabilistic planning to generate low-cost troubleshooting plans. In cooperation with Scania, progress was made in the areas of modeling [26,24], finding suitable search heuristics for use in planning for troubleshooting [12], and generating simplified models suitable for use during certain parts of the planning process, where the tradeoff between precision and performance is explored [30].

In late 2009 and 2010, the original intention was to develop a new probabilistic model for a larger scale automotive system together with Scania. Due to unforeseen circumstances at Scania, this has not yet been done. Instead, a new planning algorithm applicable to troubleshooting as well as other stochastic shortest-path problems was developed [39]. The new algorithm focuses on reducing state expansions during search. This is particularly important when expansions are expensive, as they are in the troubleshooting problem where inference in a Bayesian network is required.

Project Publications

The following publications have been published or accepted at this time.

References

[r1] Patrick Doherty. Advanced research with autonomous unmanned aerial vehicles. In Didier Dubois, Christopher Welty, and Mary-Anne Williams, editors, Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning (KR-2004), pages 731–732, Whistler, British Columbia, Canada, June 2004. AAAI Press, Menlo Park, California, USA. Extended abstract for plenary talk.

[r2] Patrick Doherty, P. Haslum, F. Heintz, T. Merz, T. Persson, and B. Wingman. A distributed architecture for intelligent unmanned aerial vehicle experimentation. In R. Alami, editor, Proceedings of the Seventh International Symposium on Distributed Autonomous Robotic Systems (DARS-2004), Toulouse, France, June 2004. Springer-Verlag.

[r3] Patrick Doherty, J. Kachniarz, and Andrzej Szałas. Using contextually closed queries for local closed-world reasoning in rough knowledge databases. In S. Pal, L. Polkowski, and A. Skowron, editors, Rough-Neuro Computing: Techniques for Computing with Words, Cognitive Technologies, chapter 9, pages 219–250. Springer-Verlag New York, 2003.

[r4] Patrick Doherty, Witold Łukaszewicz, and Andrzej Szałas. Efficient reasoning using the local closed-world assumption. In Stefano A. Cerri and Danail Dochev, editors, Proceedings of the Ninth International Conference on Artificial Intelligence: Methodology, Systems and Applications (AIMSA-2000), volume 1904 of Lecture Notes in Artificial Intelligence, pages 49–58, Varna, Bulgaria, September 2000. Springer-Verlag.

[r5] Patrick Doherty, Witold Łukaszewicz, and Andrzej Szałas. Approximative query techniques for agents using heterogeneous ontologies. In Didier Dubois, Christopher Welty, and Mary-Anne Williams, editors, Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning (KR-2004), pages 459–468, Whistler, British Columbia, Canada, June 2004. AAAI Press, Menlo Park, California, USA.

Previous Publications

[r6] Patrick Doherty, Joakim Gustafsson, Lars Karlsson, and Jonas Kvarnström. TAL: Temporal Action Logics – language specification and tutorial. Electronic Transactions on Artificial Intelligence, 2(3–4):273–306, September 1998. Available at http://www.ep.liu.se/ej/etai/1998/009/.

[r7] Patrick Doherty and Jonas Kvarnström. Tackling the qualification problem using fluent dependency constraints: Preliminary report. Linköping Electronic Articles in Computer and Information Science, 1997. Available at http://www.ep.liu.se/ea/cis/1997/016.

[r8] Patrick Doherty and Jonas Kvarnström. Tackling the qualification problem using fluent dependency constraints: Preliminary report. In Lina Khatib and Robert Morris, editors, Proceedings of the Fifth International Workshop on Temporal Representation and Reasoning (TIME-1998), pages 97–104, Los Alamitos, California, USA, May 1998. IEEE Computer Society Press.

[r9] Patrick Doherty and Jonas Kvarnström. TALplanner: An empirical investigation of a temporal logic-based forward chaining planner. In Claire Dixon and Michael Fisher, editors, Proceedings of the Sixth International Workshop on Temporal Representation and Reasoning (TIME-1999), pages 47–54, Orlando, Florida, USA, May 1999. IEEE Computer Society Press. Available at ftp://ftp.ida.liu.se/pub/labs/kplab/people/patdo/time99-final.ps.gz.

[r10] Patrick Doherty and Jonas Kvarnström. TALplanner: A temporal logic-based planner. AI Magazine, 22(3):95–102, 2001. See also http://www.aaai.org/ojs/index.php/aimagazine/issue/view/143/showToc.

[r11] Joakim Gustafsson and Jonas Kvarnström. Elaboration tolerance through object-orientation. In Proceedings of the Fifth Symposium on Logical Formalizations of Commonsense Reasoning (Common Sense-2001), 2001. Available at http://www.cs.nyu.edu/faculty/davise/commonsense01/final/kvarnstrom.ps.

[r12] Joakim Gustafsson and Jonas Kvarnström. Elaboration tolerance through object-orientation. Artificial Intelligence, 153:239–285, March 2004.

[r13] Jonas Kvarnström. VITAL. An on-line system for reasoning about action and change using TAL. Software available at /~jonkv/vital/, 1997–2005.

[r14] Jonas Kvarnström. Applying domain analysis techniques for domain-dependent control in TALplanner. In Malik Ghallab, Joachim Hertzberg, and Paolo Traverso, editors, Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS-2002), pages 101–110, Toulouse, France, April 2002. AAAI Press, Menlo Park, California, USA.

[r15] Jonas Kvarnström. TALplanner and Other Extensions to Temporal Action Logic. PhD thesis, Linköpings universitet, April 2005. Linköping Studies in Science and Technology, Dissertation no. 937.

[r16] Jonas Kvarnström and Patrick Doherty. Tackling the qualification problem using fluent dependency constraints. Computational Intelligence, 16(2):169–209, 2000.

[r17] Jonas Kvarnström and Patrick Doherty. TALplanner: A temporal logic based forward chaining planner. Annals of Mathematics and Artificial Intelligence, 30:119–169, 2000.

[r18] Jonas Kvarnström, Patrick Doherty, and Patrik Haslum. Extending TALplanner with concurrency and resources. In Werner Horn, editor, Proceedings of the Fourteenth European Conference on Artificial Intelligence (ECAI-2000), Frontiers in Artificial Intelligence and Applications, pages 501–505, Berlin, Germany, August 2000. IOS Press, Amsterdam, The Netherlands. Available at ftp://ftp.ida.liu.se/pub/labs/kplab/people/patdo/www-ecai.ps.gz.

[r19] Jonas Kvarnström and Martin Magnusson. TALplanner in the Third International Planning Competition: Extensions and control rules. Journal of Artificial Intelligence Research, 20:343–377, December 2003. Available at http://www.jair.org/vol/vol20.html.