Temporal Reasoning for a Collaborative Planning Agent in a Dynamic Environment

We present a temporal reasoning mechanism for an individual agent situated in a dynamic environment such as the web and collaborating with other agents while interleaving planning and acting. Building a collaborative agent that can flexibly achieve its goals in changing environments requires a blending of real-time computing and AI technologies. Therefore, our mechanism consists of an Artificial Intelligence (AI) planning subsystem and a Real-Time (RT) scheduling subsystem. The AI planning subsystem is based on a model for collaborative planning. The AI planning subsystem generates a partial order plan dynamically. During the planning it sends the RT scheduling subsystem basic actions and time constraints. The RT scheduling subsystem receives the dynamic basic actions set with associated temporal constraints and inserts these actions into the agent's schedule of activities in such a way that the resulting schedule is feasible and satisfies the temporal constraints. Our mechanism allows the agent to construct its individual schedule independently. The mechanism handles various types of temporal constraints arising from individual activities and its collaborators. In contrast to other works on scheduling in planning systems which are either not appropriate for uncertain and dynamic environments or cannot be expanded for use in multi-agent systems, our mechanism enables the individual agent to determine the time of its activities in uncertain situations and to easily integrate its activities with the activities of other agents. We have proved that under certain conditions temporal reasoning mechanism of the AI planning subsystem is sound and complete. We show the results of several experiments on the system. The results demonstrate that interleave planning and acting in our environment is crucial.     

Group planning with time constraints

Embedding planning systems in real-world domains has led to the necessity of Distributed Continual Planning (DCP) systems where planning activities are distributed across multiple agents and plan generation may occur concurrently with plan execution. A key challenge in DCP systems is how to coordinate activities for a group of planning agents. This problem is compounded when these agents are situated in a real-world dynamic domain where the agents often encounter differing, incomplete, and possibly inconsistent views of their environment. To date, DCP systems have only focused on cases where agents’ behavior is designed to optimize a global plan. In contrast, this paper presents a temporal reasoning mechanism for self-interested planning agents. To do so, we model agents’ behavior based on the Belief-Desire-Intention (BDI) theoretical model of cooperation, while modeling dynamic joint plans with group time constraints through creating hierarchical abstraction plans integrated with temporal constraints network. The contribution of this paper is threefold: (i) the BDI model specifies a behavior for self interested agents working in a group, permitting an individual agent to schedule its activities in an autonomous fashion, while taking into consideration temporal constraints of its group members; (ii) abstract plans allow the group to plan a joint action without explicitly describing all possible states in advance, making it possible to reduce the number of states which need to be considered in a BDI-based approach; and (iii) a temporal constraints network enables each agent to reason by itself about the best time for scheduling activities, making it possible to reduce coordination messages among a group. The mechanism ensures temporal consistency of a cooperative plan, enables the interleaving of planning and execution at both individual and group levels. We report on how the mechanism was implemented within a commercial training and simulation application, and present empirical evidence of its effectiveness in real-life scenarios and in reducing communication to coordinate group members’ activities.     

Sensor planning with Bayesian decision theory

In this paper ongoing work on an approach for planning sensing actions and controlling intelligent, purposive robotic systems is presented. The method uses Bayesian decision analysis (BDA) for deciding what sensing actions should be performed. This offers a probabilistic framework that provides a more dynamic and modular behaviour than traditional rule based planners. Experiments show that the Bayesian sensor planning strategy is capable of controlling an autonomous mobile robot operating in partly known environments.     

A framework for cooperative work: An approach based on the intentionality

The aim of this work is to elaborate rational interaction between intelligent systems, particularly when these systems have to resolve together a given task.Firstly, inherent problems of distributed problem solving are discussed. In the centre of these problems emerges on one hand, the difficulty in building an organizational structure and its dynamic for cooperative intelligent systems, and on the other hand the difficulty for the intelligent systems to know what is their degree of cooperation and what is their information exchange policy.To resolve these problems, the first part of this paper explores basic principles governing the rational balance among an agent's beliefs, actions, and intentions. Then, the second part treats the planning in the multi-agent environment. In this case, a plan is not considered as a sequence of actions executed by an agent in order to achieve his goal, but as a mental frame including his beliefs, his commitments, and his intentions. Then this planning method serves as rational interaction between intelligent systems in which the communicative acts expressed in formal language take place. Finally, the formulation of cooperative strategies between intelligent systems complete this work. These strategies are simulated and valued in the concrete environment of air traffic control.     

An abstract knowledge based approach to diagnosis and recovery of plan failure in multi-agent systems

Open multi-agent systems (MAS) are decentralised and distributed systems that consist of a large number of loosely coupled autonomous agents. In the absence of centralised control they tend to be difficult to manage, especially in an open environment, which is dynamic, complex, distributed and unpredictable. This dynamism and uncertainty in an open environment gives rise to unexpected plan failures. In this paper we present an abstract knowledge based approach for the diagnosis and recovery of plan action failures. Our approach associates a sentinel agent with each problem solving agent in order to monitor the problem solving agent’s interactions. The proposed approach also requires the problem solving agents to be able to report on the status of a plan’s actions.Once an exception is detected the sentinel agents start an investigation of the suspected agents. The sentinel agents collect information about the status of failed plan abstract actions and knowledge about agents’ mental attitudes regarding any failed plan. The sentinel agent then uses this abstract knowledge and the agents’ mental attitudes, to diagnose the underlying cause of the plan failure. The sentinel agent may ask the problem solving agent to retry their failed plan based on the diagnostic result.     

Behaviourally rich actions for user-controlled characters

The increasing use of animated characters and avatars in computer games and 3D online worlds requires increasingly complex behaviour with increasingly simple and easy to use control systems. This paper presents a system for user-controlled actions that aims at simplicity and ease of use while being enhanced by modern animation techniques to produce rich and complex behaviour. We use inverse kinematics based motion adaptation to make pre-existing pieces of motion apply to new targets. The expressiveness of the character is enhanced by adding autonomous behaviour, in this case eye gaze behaviour. This behaviour is generated autonomously but is still influenced by the actions that the user is requesting the character to perform. The actions themselves are simple for a designer with no programming experience to design and for an end user to customise. They are also very simple to invoke.     

Multi-agent collaboration in time-constrained domains

Timeliness is usually an indispensable attribute of planning and problem solving for resource allocation in command, control and communication systems. The success of such a system is judged on its ability to respond to scheduled and unscheduled tasks within a permissible time period. The response is based on a plan that covers the following activities: resource allocation, plan execution and monitoring and dynamic plan mending, if necessary. Decision making for resource selection can become very time consuming when there are many resources and the number of constraints is large. In a changing environment of multiple agents, restrictive organizational structures and strict communication protocols may cause intolerable further delays.Traditional approaches to planning in deterministic environments require a predictable amount of time to produce and execute plans. However, given more time, such systems usually cannot improve on the plans. In this paper we describe a multi-agent resource scheduler which uses a prioritized rule base to model decision making under the constraints of time. We also discuss dynamic scoping as a negotiation technique for inter-agent cooperation and constrained lattice-like communications as an optimized message routing strategy. Finally, we present some empirical results from a sequence of experiments.     

Supervenient hierarchies of behaviours-from robot vacuuming to space telerobotics

In this paper we describe the use of behaviour hierarchies based on ‘merging’ two models of multi-layer architecture—the supervenience model and the subsumption model. The behaviour hierarchy approach allows us to use the robustness of reactivity in behaviour design. It also encourages the design of modular behaviours that can be reused or more importantly recalibrated in different situations. We argue that behaviour hierarchies extend our ability to design and programme effective solutions that combine reactive and goal-driven components, but do not require any explicit planning. This work is used for two implemented systems in which autonomous mobile robots perform a vacuuming task and object tracking in support of a space telerobotics system.     

Parallelized egocentric fields for autonomous navigation

In this paper, we propose a general framework for local path-planning and steering that can be easily extended to perform high-level behaviors. Our framework is based on the concept of affordances: the possible ways an agent can interact with its environment. Each agent perceives the environment through a set of vector and scalar fields that are represented in the agent’s local space. This egocentric property allows us to efficiently compute a local space-time plan and has better parallel scalability than a global fields approach. We then use these perception fields to compute a fitness measure for every possible action, defined as an affordance field. The action that has the optimal value in the affordance field is the agent’s steering decision. We propose an extension to a linear space-time prediction model for dynamic collision avoidance and present our parallelization results on multicore systems. We analyze and evaluate our framework using a comprehensive suite of test cases provided in SteerBench and demonstrate autonomous virtual pedestrians that perform steering and path planning in unknown environments along with the emergence of high-level responses to never seen before situations.     

Towards a Trajectory Planning Concept: Augmenting Path Planning Methods by Considering Speed Limit Constraints

Trajectory planning is an essential part of systems controlling autonomous entities such as vehicles or robots. It requires not only finding spatial curves but also that dynamic properties of the vehicles (such as speed limits for certain maneuvers) must be followed. In this paper, we present an approach for augmenting existing path planning methods to support basic dynamic constraints, concretely speed limit constraints. We apply this approach to the well known A* and state-of-the-art Theta* and Lazy Theta* path planning algorithms. We use a concept of trajectory planning based on a modular architecture in which spatial and dynamic parts can be easily implemented. This concept allows dynamic aspects to be processed during planning. Existing systems based on a similar concept usually add dynamics (velocity) into spatial curves in a post-processing step which might be inappropriate when the curves do not follow the dynamics. Many existing trajectory planning approaches, especially in mobile robotics, encode dynamic aspects directly in the representation (e.g. in the form of regular lattices) which requires a precise knowledge of the environmental and dynamic properties of particular autonomous entities making designing and implementing such trajectory planning approaches quite difficult. The concept of trajectory planning we implemented might not be as precise but the modular architecture makes the design and implementation easier because we can use (modified) well known path planning methods and define models of dynamics of autonomous entities separately. This seems to be appropriate for simulations used in feasibility studies for some complex autonomous systems or in computer games etc. Our basic implementation of the augmented A*, Theta* and Lazy Theta* algorithms is also experimentally evaluated. We compare (i) the augmented and basic A*, Theta* and Lazy Theta* algorithms and (ii) optimizing of augmented Theta* and Lazy Theta* for distance (the trajectory length) and duration (time needed to move through the trajectory).     

Online motion planning for unexplored underwater environments using autonomous underwater vehicles

We present an approach to endow an autonomous underwater vehicle with the capabilities to move through unexplored environments. To do so, we propose a computational framework for planning feasible and safe paths. The framework allows the vehicle to incrementally build a map of the surroundings, while simultaneously (re)planning a feasible path to a specified goal. To accomplish this, the framework considers motion constraints to plan feasible 3D paths, that is, those that meet the vehicle’s motion capabilities. It also incorporates a risk function to avoid navigating close to nearby obstacles. Furthermore, the framework makes use of two strategies to ensure meeting online computation limitations. The first one is to reuse the last best known solution to eliminate time‐consuming pruning routines. The second one is to opportunistically check the states’ risk of collision. To evaluate the proposed approach, we use the Sparus II performing autonomous missions in different real‐world scenarios. These experiments consist of simulated and in‐water trials for different tasks. The conducted tasks include the exploration of challenging scenarios such as artificial marine structures, natural marine structures, and confined natural environments. All these applications allow us to extensively prove the efficacy of the presented approach, not only for constant‐depth missions (2D), but, more important, for situations in which the vehicle must vary its depth (3D).     

Are some human ecosystems self-defeating?

Complex patterns of human behaviour are difficult to capture in agent-based simulations of socio-ecological systems. Even knowing each individual agent's strategy at one point in time may not help when trying to predict the collective behaviour of certain systems – e.g. if it is in each agent's best interest to do the opposite of most other agents. In self-defeating situations like these, the collective population of agents may exhibit a panorama of simple or complex behaviour, depending on the extent to which useful information is shared. An extreme example is the bar problem, in which a simulated population of bar attendees oscillates in a seemingly random manner around a critical congestion level. This paper suggests that several resource management problems involving human interactions with ecosystems may possess a self-defeating character. This poses new challenges for integrated resources management. A case in point is the potential over-fishing of fisheries, which is addressed in the paper and likened to a minority game. It is concluded that a mix of innovative and imitative behaviour may be the key to overcoming self-defeating tendencies.     

实时专家系统中反应—规划—动作的集成

以AMPE模型为基础,探讨了在动态环境下AI系统如何集成响应执行和规划生成的问题。AMPE模型是从实际应用中演化出的AI模型,采用分离结构,在规划中引入一类被称为观察点的特殊行为,支持异步重规划。描述了AMPE的各类规划行为的形式和消息的基本结构。给出一个规划表示的实例。     

Model-driven performance prediction of systems of systems

Systems of systems exhibit characteristics that pose difficulty in modelling and predicting their overall performance capabilities, including the presence of operational independence, emergent behaviour, and evolutionary development. When considering systems of systems within the autonomous defence systems context, these aspects become increasingly critical, as constraints on the performance of the final system are typically driven by hard constraints on space, weight and power. System execution modelling languages and tools permit early prediction of the performance of model-driven systems; however, the focus to date has been on understanding the performance of a model rather than determining whether it meets performance requirements, and only subsequently carrying out analysis to reveal the causes of any requirement violations. Moreover, such an analysis is even more difficult when applied to several systems cooperating to achieve a common goal—a system of systems. In this article, we propose an integrated approach to performance prediction of model-driven real-time embedded defence systems and systems of systems. Our architectural prototyping system supports a scenario-driven experimental platform for evaluating model suitability within a set of deployment and real-time performance constraints. We present an overview of our performance prediction system, demonstrating the integration of modelling, execution and performance analysis, and discuss a case study to illustrate our approach.     

Planning and execution through variable resolution planning

Generating sequences of actions–plans–for robots using Automated Planning in stochastic and dynamic environments has been shown to be a difficult task with high computational complexity. These plans are composed of actions whose execution might fail due to different reasons. In many cases, if the execution of an action fails, it prevents the execution of some (or all) of the remainder actions in the plan. Therefore, in most real-world scenarios computing a complete and sound (valid) plan at each (re-)planning step is not worth the computational resources and time required to generate the plan. This is specially true given the high probability of plan execution failure. Besides, in many real-world environments, plans must be generated fast, both at the start of the execution and after every execution failure. In this paper, we present Variable Resolution Planning which uses Automated Planning to quickly compute a reasonable (not necessarily sound) plan. Our approach computes an abstract representation–removing some information from the planning task–which is used once a search depth of $k$ steps has been reached. Thus, our approach generates a plan where the first $k$ actions are applicable if the domain is stationary and deterministic, while the rest of the plan might not be necessarily applicable. The advantages of this approach are that it: is faster than regular full-fledged planning (both in the probabilistic or deterministic settings); does not spend much time on the far future actions that probably will not be executed, since in most cases it will need to replan before executing the end of the plan; and takes into account some information of the far future, as an improvement over pure reactive systems. We present experimental results on different robotics domains that simulate tasks on stochastic environments.     

Linear logic as a tool for planning under temporal uncertainty

The typical AI problem is that of making a plan of the actions to be performed by a controller so that it could get into a set of final situations, if it started with a certain initial situation.The plans, and related winning strategies, happen to be finite in the case of a finite number of states and a finite number of instant actions.The situation becomes much more complex when we deal with planning under temporal uncertainty caused by actions with delayed effects.Here we introduce a tree-based formalism to express plans, or winning strategies, in finite state systems in which actions may have quantitatively delayed effects. Since the delays are non-deterministic and continuous, we need an infinite branching to display all possible delays. Nevertheless, under reasonable assumptions, we show that infinite winning strategies which may arise in this context can be captured by finite plans.The above planning problem is specified in logical terms within a Horn fragment of affine logic. Among other things, the advantage of linear logic approach is that we can easily capture ‘preemptive/anticipative’ plans (in which a new action β may be taken at some moment within the running time of an action α being carried out, in order to be prepared before completion of action α).In this paper we propose a comprehensive and adequate logical model of strong planning under temporal uncertainty which addresses infinity concerns. In particular, we establish a direct correspondence between linear logic proofs and plans, or winning strategies, for the actions with quantitative delayed effects.     

A heuristic search approach to planning with temporally extended preferences

Planning with preferences involves not only finding a plan that achieves the goal, it requires finding a preferred plan that achieves the goal, where preferences over plans are specified as part of the planner's input. In this paper we provide a technique for accomplishing this objective. Our technique can deal with a rich class of preferences, including so-called temporally extended preferences (TEPs). Unlike simple preferences which express desired properties of the final state achieved by a plan, TEPs can express desired properties of the entire sequence of states traversed by a plan, allowing the user to express a much richer set of preferences. Our technique involves converting a planning problem with TEPs into an equivalent planning problem containing only simple preferences. This conversion is accomplished by augmenting the inputed planning domain with a new set of predicates and actions for updating these predicates. We then provide a collection of new heuristics and a specialized search algorithm that can guide the planner towards preferred plans. Under some fairly general conditions our method is able to find a most preferred plan—i.e., an optimal plan. It can accomplish this without having to resort to admissible heuristics, which often perform poorly in practice. Nor does our technique require an assumption of restricted plan length or make-span. We have implemented our approach in the HPlan-P planning system and used it to compete in the 5th International Planning Competition, where it achieved distinguished performance in the Qualitative Preferences track.     

Cooperative multi-robot belief space planning for autonomous navigation in unknown environments

We investigate the problem of cooperative multi-robot planning in unknown environments, which is important in numerous applications in robotics. The research community has been actively developing belief space planning approaches that account for the different sources of uncertainty within planning, recently also considering uncertainty in the environment observed by planning time. We further advance the state of the art by reasoning about future observations of environments that are unknown at planning time. The key idea is to incorporate within the belief indirect multi-robot constraints that correspond to these future observations. Such a formulation facilitates a framework for active collaborative state estimation while operating in unknown environments. In particular, it can be used to identify best robot actions or trajectories among given candidates generated by existing motion planning approaches, or to refine nominal trajectories into locally optimal paths using direct trajectory optimization techniques. We demonstrate our approach in a multi-robot autonomous navigation scenario and consider its applicability for autonomous navigation in unknown obstacle-free and obstacle-populated environments. Results indicate that modeling future multi-robot interaction within the belief allows to determine robot actions (paths) that yield significantly improved estimation accuracy.     

Agent's actions as a classification criteria for the state space in a learning from rewards system

We focus in this paper on the problem of learning an autonomous agent's policy when the state space is very large and the set of actions available is comparatively short. To this end, we use a non-parametric decision rule (concretely, a nearest-neighbour strategy) in order to cluster the state space by means of the action that leads to a successful situation. Using an exploration strategy to avoid greedy behaviour, the agent builds clusters of positively-classified states through trial and error learning. In this paper, we implement a 3D synthetic agent which plays an ‘avoid the asteroid’ game that suits our assumptions. Using as the state space a feature vector space extracted from a visual navigation system, we test two exploration strategies using the trial and error learning method. This experiment shows that the agent is a good classifier over the state space, and will therefore show good behaviour in its synthetic world.     

Identifying competences for the design of systems supporting complex decision-making tasks: a managerial planning application

The work presented in this paper is addressed to the front-end phases of the development of a system supporting a complex decision-making task: high-level managerial planning in small-to-medium enterprises (SMEs). It attempts to identify characteristics of the competences possessed by experienced managers and used when taking high-level managerial planning decisions, and to assess their potential implications for system design. The work is based on the assumption that the design of effective systems supporting complex decision-making tasks in a specific domain, would require elicitation of competences possessed by experienced persons in the domain, especially those related to the mental processes followed when confronting the cognitive constraints involved in the specific decision-making environment. Such an investigation would lead to the development of systems improving decision making since they would (1) respond to the difficulties met by potential users in performing complex decision-making tasks; (2) reduce possible negative consequences of users' decision-making competences; and (3) at the same time they would achieve the required compatibility with users' mental processes. The research methodology was based on a planning scenario and on an analysis of verbal protocols obtained from a sample of small-enterprise managers confronted with this scenario. Results provide evidence about (1) the type of decisions and actions taken by experienced managers when confronted with the cognitive constraints involved in managerial planning situations; (2) phases and sequence of the process of arriving at planning decisions; and (3) data used and types of analyses performed. Some general implications are drawn from these results with respect to the configuration of a system aiming at supporting managerial planning. These refer to the type of support to be provided at various phases of the planning process, possible features of the human-computer interface, and generic or task/user specific aspects of the system.