Abstract: Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems where some durations are uncontrollable (determined by nature), as is often the case for actions in planning. It is es-sential to verify that such networks are dynamically controllable (DC) – executable regardless of the outcomes of uncontrollable durations – and to convert them to an executable form. We use insights from incremental DC verification algorithms to re-analyze the original verification algorithm. This algorithm, thought to be pseudo-polynomial and subsumed by an O(n5) algorithm and later an O(n4) algorithm, is in fact O(n4) given a small modification. This makes the algorithm attractive once again, given its basis in a less complex and more intuitive theory. Finally, we discuss a change reducing the amount of work performed by the algorithm. 1

It is generally hard to predict the exact duration of an action. Uncertainty in durations is often modeled in temporal planning by the use of upper bounds on durations, with the assumption that if an action happens to be executed more quickly, the plan will still succeed. However, this assumption is often false: If we finish cooking too early, the dinner will be cold before everyone is ready to eat. Simple Temporal Problems with Uncertainty (STPUs) allow us to model such situations. An STPU-based planner must verify that the plans it generates are executable, captured by the property of dynamic controllability. The Efficient IDC (EIDC) algorithm can do this incrementally during planning, with an amortized complexity per step of O(n3) but a worst-case complexity per step of O(n4). In this paper we show that the worst-case run-time of EIDC does occur, leading to repeated reprocessing of nodes in the STPU while verifying the dynamic controllability property. We present a new version of the algorithm, EIDC2, which through optimal ordering of nodes avoids the need for reprocessing. This gives EIDC2 a strictly lower worst-case run-time, making it the fastest known algorithm for incrementally verifying dynamic controllability of STPUs.

Mission planning for collaborative Unmanned Aircraft Systems (UAS:s) is a complex topic which involves trade-offs between the degree of centralization or decentralization required, the degree of abstraction in which plans are generated, and the degree to which such plans are distributed among participating UAS:s. In realistic environments such as those found in natural and man-made catastrophes where emergency services personnel are involved, a certain degree of centralization and abstraction is necessary in order for those in charge to understand and eventually sign off on potential plans. It is also quite often the case that unconstrained distribution of actions is inconsistent with the loosely coupled interactions and dependencies which arise between collaborating systems. In this article, we present a new planning algorithm for collaborative UAS:s based on combining ideas from forward chaining planning with partial-order planning leading to a new hybrid partial order forward-chaining (POFC) framework which meets the requirements on centralization, abstraction and distribution we find in realistic emergency services settings.

An important use of unmanned aerial vehicles is surveillance of distant targets, where sensor information must quickly be transmitted back to a base station. In many cases, high uninterrupted bandwidth requires line-of-sight between sender and transmitter to minimize quality degradation. Communication range is typically limited, especially when smaller UAVs are used. Both problems can be solved by creating relay chains for surveillance of a single target, and relay trees for simultaneous surveillance of multiple targets. In this paper, we show how such chains and trees can be calculated. For relay chains we create a set of chains offering different trade-offs between the number of UAVs in the chain and the chain's cost. We also show new results on how relay trees can be quickly calculated and then incrementally improved if necessary. Encouraging empirical results for improvement of relay trees are presented.

Autonomous systems situated in the real world often need to recognize, track, and reason about various types of physical objects. In order to allow reasoning at a symbolic level, one must create and continuously maintain a correlation between symbols labeling physical objects and the sensor data being collected about them, a process called anchoring. In this paper we present a stream-based hierarchical anchoring framework extending the DyKnow knowledge processing middleware. A classification hierarchy is associated with expressive conditions for hypothesizing the type and identity of an object given streams of temporally tagged sensor data. The anchoring process constructs and maintains a set of object linkage structures representing the best possible hypotheses at any time. Each hypothesis can be incrementally generalized or narrowed down as new sensor data arrives. Symbols can be associated with an object at any level of classification, permitting symbolic reasoning on different levels of abstraction. The approach has been applied to a traffic monitoring application where an unmanned aerial vehicle collects information about a small urban area in order to detect traffic violations.

TALplanner is a forward-chaining planner that relies on domain knowledge in the shape of temporal logic formulas in order to prune irrelevant parts of the search space. TALplanner recently participated in the third International Planning Competition, which had a clear emphasis on increasing the complexity of the problem domains being used as benchmark tests and the expressivity required to represent these domains in a planning system. Like many other planners, TALplanner had support for some but not all aspects of this increase in expressivity, and a number of changes to the planner were required. After a short introduction to TALplanner, this article describes some of the changes that were made before and during the competition. We also describe the process of introducing suitable domain knowledge for several of the competition domains.

In the area of formal reasoning about action and change, one of the fundamental representation problems is providing concise modular and incremental specifications of action types and world models, where instantiations of action types are invoked by agents such as mobile robots. Provided the preconditions to the action are true, their invocation results in changes to the world model concomitant with the goal‐directed behavior of the agent. One particularly difficult class of related problems, collectively called the qualification problem, deals with the need to find a concise incremental and modular means of characterizing the plethora of exceptional conditions that might qualify an action, but generally do not, without having to explicitly enumerate them in the preconditions to an action. We show how fluent dependency constraints together with the use of durational fluents can be used to deal with problems associated with action qualification using a temporal logic for action and change called TAL‐Q. We demonstrate the approach using action scenarios that combine solutions to the frame, ramification, and qualification problems in the context of actions with duration, concurrent actions, nondeterministic actions, and the use of both Boolean and non‐Boolean fluents. The circumscription policy used for the combined problems is reducible to the first‐order case.