We propose a novel theoretical approach for solving a Stochastic Security Game using augmented Markov Decison Processes and an experimental evaluation. Most of the previous works mentioned in the literature focus on Linear Programming techniques seeking Strong Stackelberg Equilibria through the defender and attacker’s strategy spaces. Although effective, these techniques are computationally expensive and tend to not scale well to very large problems. By fixing the set of the possible defense strategies, our approach is able to use the well-known augmented MDP formalism to compute an optimal policy for an attacker facing a defender patrolling. Experimental results on fully observable cases validate our approach and show good performances in comparison with optimistic and pessimistic approaches. However, these results also highlight the need of scalability improvements and of handling the partial observability cases.

Adjustable Autonomy is gaining interest as it alleviates robot management costs, which often restrain non-routine applications. Whereas it seems straightforward to account for the availability of helpers when making plans that involve being granted for support in the future, no existing research covers this issue. As a solution, we formalize the first human-centric model that accounts for operator support dynamics when generating adjustable-autonomy plans. We formalize Restricted Autonomy Levels (RAL) within a Markov-based framework for representing when and what level of support the robot should ask for. This model is combined with a formalization of usual aspects of man-machine collaboration: operator availability, risk of denial and withdrawal, effect of teleoperation, risks and consequences for violating RAL restrictions and backup procedures, should violations occur. We empirically demonstrate, through a detailed example and the deployment on a professional-grade security robot, that the generated plans deeply combine the problem-solving activities of the robot with the management of requested human support, leading to improved performance and decreased operator effort. We also analyse the computational costs of computing policies that ensure a zero-chance of RAL violation.

This paper introduces Advice-MDPs, an expansion of Markov Decision Processes for generating policies that take into consideration advising on the desirability, undesirability, and prohibition of certain states and actions. AdviceMDPs enable the design of designing semi-autonomous systems (systems that require operator support for at least handling certain situations) that can efficiently handle unexpected complex environments. Operators, through advising, can augment the planning model for covering unexpected real-world irregularities. This advising can swiftly augment the degree of autonomy of the system, so it can work without subsequent human intervention. This paper details the Advice-MDP formalism, a fast AdviceMDP resolution algorithm, and its applicability for real-world tasks, via the design of a professional-class semi-autonomous robot system ready to be deployed in a wide range of unexpected environments and capable of efficiently integrating operator advising.

Most Situation Awareness applications in Information Fusion try to evaluate a dynamic environment by a passive approach combining heterogeneous information. However in a crisis situation, the decision has to be made efficiently as the world quickly evolves. A consequence is the difficulty to get the information in a fast and efficient way with an acceptable confidence. Another problem is the processing of a significant amount of heterogeneous information in near real time. To address this issue, we propose a multi-level Information Fusion framework based on Dynamic Bayesian Networks (DBN) with an active perception approach. The contribution of this model primarily lies in its capability of handling both Hard & Soft sensors and resulting information. And secondly in the identification of the most valuable DBN variables which maximize the information gains in the next step. These valuable variables allow to infer states on a sub-DBN to reduce the complexity of calculation. In this top-down approach, we seek which variables can provide the most valuable information to select automatically the right sensors and choose correct actions to optimally observe these variables. We finally propose an illustration with a basic maritime scenario.

Teamwork in decentralized systems plays a central role in recent artificial intelligence advances, such as in applications to disaster response. Decentralized partially observable Markov decision processes (Dec-POMDPs) have emerged as the de facto standard mathematical framework to study and optimally plan in sequentially decentralized multiagent systems under uncertainty. In this work, we focus our analysis on team formation and reformation in Decentralized POMDPs with a new model coined Team-POMDPs. We present some interesting structural properties of this model inherited from the field of cooperative game theory. We introduce a Monte Carlo-based planning algorithm to learn locally optimal team-reformation policies that tell our agents how to dynamically rearrange in order to better deal with the evolution of the task at hand. By reforming the team during execution, our experiments show that we are able to achieve higher expected long-term rewards than with stationary teams.

Many real-world multi-agent applications such as rescue operations require to dynamically assemble or disassemble teams to provide a service exploiting this flexibility. While Dec-POMDPs capture real-world uncertainty in multi-agent systems, they fail to use the team flexibility. This paper introduces a new model, called the Open Dec-POMDP, allowing us to consider agents that can enter and leave the system during the execution of the process. Exploiting the team flexibility enables us to present a new best-response dynamics' algorithm that uses Monte Carlo simulations to compute joint policies. Our algorithm can dynamically adapt to the team flexibility and computes locally optimal solutions. Experiments demonstrate that Open Dec-POMDP solutions compare favorably on different fire-fighting scenarios to standard Dec-POMDPs'.

Most of existing coordination techniques for autonomous agents assume the knowledge or the estimation of the other agents' policy. However, this assumption is not valid in semi-autonomous agents because an external entity can take the control and modify the behavior of the agent. We face this problem in applications where an operator can take the control of the system (Robot/UAV). Many human factors may affect this behavior, such as stress, hesitations and preferences. Estimating the policy in such contexts is a difficult problem. Many existing algorithms using Inverse Reinforcement learning or imitation have been developed. However most of them have weak performance when non-optimal policy is followed. In this paper, we investigate techniques for estimating the followed policies of semi-autonomous agents that could be nonoptimal due to critical situations We extend some prediction methods and algorithms based on Factored MDPs and Inverse Reinforcement Learning to improve their stability and their efficiency during the execution of a mission. Then, we develop various experiments showing the performance on efficiency and stability of our approach in different conditions and comparing with it.

Threat assessment is a high-level information fusion task which supports a decision maker in achieving a proper level of situational awareness. In this paper, we propose an approach to threat assessment that fuses both game-theoretic behavior modeling and adversarial intention recognition. In adversarial situations, where two opposing forces are competing to achieve conflicting goals in a shared environment, the behavior of the observed adversary will not only depend on the goal it is trying to achieve, but also on the decisions of its opponent. We model the planning process of such a goal-directed adversary as an Attack Stochastic Game and show how we can infer its intention by inverting this model. We evaluate the potential of our approach for early and accurate intention recognition on an illustrative scenario where a decision maker has to defend a set of valuable assets against an attacker, and we discuss planned extensions.

Sequential decision problems that involve multiple objectives are prevalent. Consider for example a driver of a semi-autonomous car who may want to optimize competing objectives such as travel time and the effort associated with manual driving. We introduce a rich model called Lexicographic MDP (LMDP) and a corresponding planning algorithm called LVI that generalize previous work by allowing for conditional lexicographic preferences with slack. We analyze the convergence characteristics of LVI and establish its game theoretic properties. The performance of LVI in practice is tested within a realistic benchmark problem in the domain of semi-autonomous driving. Finally, we demonstrate how GPU-based optimization can improve the scalability of LVI and other value iteration algorithms for MDPs.

Event exploration is the process of exploring a topologically known environment to gather information about dynamic events in this environment. Using multi-robot systems for event exploration brings major challenges such as finding and communicating relevant information. This paper presents a solution to these challenges in the form of a distributed decision-theoretic model called MAPING (Multi-Agent Planning for INformation Gathering), in which each agent computes a communication and an exploration strategy by assessing the relevance of an observation for another agent. The agents use an extended belief state that contains not only their own beliefs but also approximations of other agents' beliefs. MAPING includes a forgetting mechanism to ensure that the event-exploration remains open-ended. To overcome the resolution complexity due to the extended belief state we use a method based on the well-known adopted assumption of variables independence. We evaluate our approach on different event exploration problems with varying complexity. The experimental results on simulation show the effectiveness of MAPING, its ability to scale up and its ability to face real-word applications.

Recent works on multi-agent sequential decision making using decentralized partially observable Markov decision processes have been concerned with interaction-oriented resolution techniques and provide promising results. These techniques take advantage of local interactions and coordination. In this paper, we propose an approach based on an interaction-oriented resolution of decentralized decision makers. To this end, distributed value functions (DVF) have been used by decoupling the multi-agent problem into a set of individual agent problems. However existing DVF techniques assume permanent and free communication between the agents. In this paper, we extend the DVF methodology to address full local observability, limited share of information and communication breaks. We apply our new DVF in a real-world application consisting of multi-robot exploration where each robot computes locally a strategy that minimizes the interactions between the robots and maximizes the space coverage of the team even under communication constraints. Our technique has been implemented and evaluated in simulation and in real-world scenarios during a robotic challenge for the exploration and mapping of an unknown environment. Experimental results from real-world scenarios and from the challenge are given where our system was vice-champion.

This paper addresses the problem of exploring an unknown area with a team of autonomous robots using decentralized decision making techniques. The localization aspect is not considered and it is assumed the robots share their positions and have access to a map updated with all explored areas. A key problem is then the coordination of decentralized decision processes: each individual robot must choose appropriate exploration goals so that the team simultaneously explores different locations of the environment. We formalize this problem as a Decentralized Markov Decision Process (Dec-MDP) solved as a set of individual MDPs, where interactions between MDPs are considered in a distributed value function. Thus each robot computes locally a strategy that minimizes the interactions between the robots and maximizes the space coverage of the team. Our technique has been implemented and evaluated in real-world and simulated experiments.

A* is the algorithm of finding the shortest path between two nodes in a graph. When the searching problem is constituted of a set of linked graphs, A* searches solution like if it is face of one graph formed by linked graphs. While researchers have developed solutions to reduce the execution time of A* in multiple cases by multiples techniques, we develop a new algorithm: DEC-A* which is a decentralized version of A* composing a solution through a collection of graph. A* uses a distance-plus-cost heuristic function to determine the order in which the search visits nodes in the tree. Our algorithm DEC-A* extends the evaluation of the distance-plus-cost heuristic to be the sum of two functions : local distance, which evaluates the cost to reach the nearest neighbor node s to the goal, and global distance which evaluates the cost from s to the goal through other graphs. DEC-A* reduces the time of finding the shortest path and reduces the complexity, while ensuring the privacy of graphs.

The ability to automatically answer a request that requires the composition of a set of web services has received much interest in the last decade, as it supports B2B applications. It aims at selecting and inter-connecting services provided by differ

In this paper, we describe an approach of platoon formation for planet exploration like problems. In such problems, the agents have partial observability about their environment (using on-board sensors), must deal with uncertain outcomes of their actions (a wheel could slip) and can not communicate (it uses too much energy). In order to address those limitations, we use 2V-DEC-MDP: this model deals with such problems and uses local interactions between agents instead of explicit coordinations. First, we describe how to use specific flocking rules in a 2V-DEC-MDP to build a platoon shape. Second, we use the stochastic games theory to analyze the optimality of our approach. Then, we show how we can effectively compute good policies with a low complexity. We finally give a practical usage example of our approach, on a platooning problem.

The establishment of a self-healing agent has received much interest in multiple domains such as : Web services, production supply chain, transport systems, etc. This agent has a set of actions. Its role is to respond to user request with a plan of composed actions, to on-line diagnose the status of the plan execution and to automatically repair the plan when a fault is detected during the plan's execution. To this end, three main areas are studied and modeled for the establishment of such an agent : composition, diagnosis and repair.

Cooperative control can help overcome the limitations of autonomous systems (AS) by introducing a supervision unit (SU) (human or another system) into the control loop and creating adjustable autonomy. We present a decision-theoretic approach to accomplish this using Mixed Markov Decision Processes (MI-MDPs). The solution is an optimal plan that tells the AS what actions to perform as well as when to request SU attention or transfer control to the SU. This provides a varying degree of autonomy, particularly suitable for robots exploring a domain with regions that are too complex or risky for autonomous operation, or intelligent vehicles operating in heavy traffic.

In the era of Internet-based services, companies increasingly use Web technologies to interact. Due to the inherent heterogeneity both at data and process level, ensuring interoperability between Information Systems is difficult. To automate electronic exchanges between businesses, the classical approach is to follow strictly at runtime a common interacting protocol that must be defined beforehand. This imposes a costly design time and a constrained runtime. Our goal is to propose a mediation platform that allows partners to engage directly into business-to-business exchanges. In this paper we present a multi-agent system developed with an institutional extension of the JADE development framework. Agents of the platform dynamically monitor the exchanges by interpreting business interacting actions according to each enterprise's business logic and behave in order to fulfill the business transaction.

The ability to automatically answer a request that requires the composition of a set of web services has received much interest in the last decade, as it supports B2B applications. Planning techniques are used widely in the literature to describe the web services composition problem but they don't scale up well. This weakness is due to the search space explosion caused by the large ranges of data exchanged among services. In addition, it is more interesting to use a decentralised planner because the nature of the problem is distributed. In this paper, we consider a set of web service agents where each agent has a set of services organised in a graph. To respond to a request, agents propose their best local partial plans which are partial paths in the graph. They then coordinate their partial plans to provide the global plan for the submitted request using an algorithm based on a distributed heuristic function. This function ensures the optimality and the completeness of the algorithm. Indeed, it is based not only on the agent capabilities to respond to a request, but also taking into account the plans proposed by other agents. The complexity of the algorithm is polynomial. The experiments show the ability of our approach to find the optimal solutions for automated web services composition taking into account the dependencies betwen the agents.

An important number of planning approaches have been proposed to tackle the problem of Web services composition which aims at selecting and inter-connecting services provided by different partners in response to client request. This process is beyond the human ability to analyse and generate the composition manually. Planning techniques are used widely in the literature to automatically compose web services but they don't scale up well. This weakness is due to the search space explosion caused by using the state-space or the plan-space planning techniques without take into account the distribution nature of web services domain. In a previous work, we proposed a decentralised multi-agent approach to solve the problem by associating a planning agent to each web services. Agent organises its services in a graph and respond to requests by its best partial plan extracted basing on a local heuristic. This approach is complete if the agents are independant. In this paper, we extend our previous approach by introducing a global heuristic to ensure the completeness and the optimality of the decentralised approach even if agents are dependent. The complexity of the new distributed algorithm is polynomial. This global heuristic of evaluating the best local plan avoids the wells by considering the intermediate local plans offered by other agents. To respond to a request, agents propose their best local plans basing on a distributed heuristic function. They then coordinate their partial plans by merging them to provide a global one for the submitted request.

In the last decade, there has been significant progress on Robotics. This development has widened the intervention fields of robots, particularly the assistance and interaction with humans. Improving the quality of this interaction requires robots to be endowed with representation and/or reasoning system for spatial knowledge. Our goal is to develop a planner allowing us to use human robot interaction to solve space sharing problems. This work is original, in that the representation of the same space for humans (symbolic, fuzzy) and robots (numeric) is not the same. Our objective is to combine human and robots representations of space in order to develop a mixed reasoning. We propose here an ontology called \textit{Space Ontology} as a spatial knowledge representation and reasoning system. In this paper, we focus on this ontology, and show how this type of knowledge can be profitably used for task planning. Our objective is to incorporate this ontology into a planner by extending the planning language PDDL.

We present a new framework for controlling a robot collaborating with a human to accomplish a common mission. Knowing that we are interested in collaboration domains where there is no shared plan between the human and the robot, the constraints on the decision process are more challenging. We study the decision process of a robot agent for a specific shared mission with a human considering the effect of the human presence, the planning flexibility according to human comfortability and achieving mission. We choose to formalize this problem with Partially Observable Markov Decision Process, then we describe a new domain example that represent human-robot collaboration with no shared plan and we show some preliminary results of solving the POMDP model with standard optimal algorithms as a base work to compare with state-of-the-art and future-work approximate algorithms.

Automated composition of Web services has received much interest in the last decade, as it supports B2B applications. It aims at selecting and inter-connecting services provided by different partners in response to client requests. Planning techniques are used widely in the literature to describe Web services composition problem. However, since Web services proliferate day after day, classical planners are no longer well suited to compose Web services in a reasonable time. This weakness is due to the explosion of the search space caused by the large number of services and the broad range of data exchanged among services. In this paper, we propose a decentralised multi-agent approach to solve the Web services composition problem at runtime. Our model consists of a set of Web service agents where each agent has a set of services organised in a graph. Responding to a request, agents propose partial plans which are partial paths in the graph, then they coordinate their partial plans to provide the best global plan for the submitted request. The analysis of the complexity and results of the implementation show the ability of our approach to scale up when compared to the of state-of-the-art techniques for automated web service composition.

WS are distributed software components that can be exposed and invoked over the Internet using standard protocols. They communicate with their clients and with other WS by sending XML based messages over the Internet. AI planning techniques can help solving the composition of WS problem. In fact, services can be modelled as actions and the business process as planning to connect the WS. The main contribution of this paper is the extension of the model of actions to handle the creation or elimination of objects as effects of actions. This contribution allows us to answer to new and more expressive requests, called implicit requests, in which goals may contain objects that have been generated by the plan.

Unlike mono-agent systems, multi-agent planing addresses the problem of resolving conflicts between individual and group interests. In this paper, we are using a Decentralized Vector Valued Markov Decision Process (2V-DEC-MDP) in order to solve this problem. It uses an utility function which is returning a vector representing both individual and group interest. The individual interest of an agent, computed off-line, is based on its optimal policy. The group interest is computed on-line by the agents using their own local observations. In order to take into account both criteria in a decision process and to find a good trade-off between the group interest and the agent's one, we developed a regret-based algorithm based on the Tchebychev Norm.

A considerable amount of attention has been paid to the coalition formation problem to deal efficiently with tasks needing more than one agent. However, little attention has been paid to the problem of monitoring a coalition during the execution by modifying it according to the progress of the accomplishment of the task. In this paper, we consider a coalition of resource-bounded autonomous agents with anytime behavior solving a common complex task. There is no central control component. Agents can observe the effect of the other agents' actions. They can decide whether they should continue to contribute in solving the common task or to stop their contribution and to leave the coalition. This decision is made in a distributed way. The objective is to avoid the waste of resources and time by using the same coalition along the task accomplishment while some agents become not necessary to pursue the accomplishment of the task. We formalize this decentralized decision making problem as a DEC-MDP.

This paper presents a new approach to multi-agent planning under temporal constraints and uncertainty of admissible operations. A planning problem in AI is usually specified as follows: given a description of the current state of some system, a set of actions that can be performed on the system and a description of a goal set of states for the system, find a sequence of actions that can be performed to transform the system into one of the goal states. The problem described in this paper is to find a way to reach a set of goals satisfying all specified constraints. By constraints, we mean temporal constraints and other constraints in the form of costs, number of agents, etc. Temporal constraints concern both qualitative and quantitative aspects of the system. We consider a set of agents, a set of goals and a description of the environment. The objective is, for one or more agents, to execute a set of tasks to satisfy all goals while respecting all the constraints. A planning procedure over AND-OR graphs is used to generate plans. The proposed multi-agent planning method is based on a centralized scheme in which all the coordination is done at a central location and the agents have no autonomy at the planning level. A specific feature of the task statement in this paper is that we aim at solving tasks of planning and scheduling, the complexity of which is conditioned by temporal and other constraints.

Most of works on planning under uncertainty in AI assumes rather simple action models, which do not consider multiple resources. This assumption is not reasonable for many applications such as planetary rovers or robotics which cope with much uncertainty about the duration of tasks, the energy, and the data storage. In this paper, we outline an approach to control the operation of an autonomous rover which operates under multiple resource constraints. We consider a directed acyclic graph of progressive processing tasks with multiple resources, for which an optimal policy is obtained by solving a corresponding Markov decision process (MDP). Computing an optimal policy for an MDP with multiple resources makes the search space large. We cannot calculate this optimal policy at run-time. The approach developed in this paper overcomes this difficulty by combining: decomposition of a large MDP into smaller ones, compression of the state space by exploiting characteristics of the multiple resources constraint, construction of local policies for the decomposed MDPs using state space discretization and resource compression, and recomposition of the local policies to obtain a near optimal global policy. Finally, we present first experimental results showing the feasibility and performances of our approach.

In this paper, we study the problem of optimizing multi-objective decision-theoretic path planning. We transform this problem in a Markov decision process with a multi-dimensional value function. We also show that dealing with resource-bounded path planning consists of considering a complementary objective that is the minimization of resource consumption. We describe techniques that allow to derive an optimal policy where it is hard to express the expected utilities, rewards and values with a numerical measure. Firstly, we present approaches based on egalitarian social welfare techniques and secondly we examine different approaches based on preferences and we define notions of optimally with preferred solutions.

This paper presents the multistage negotiation protocol that contributes to a more sophisticated distributed scheduling for progressive reasoning. This reasoning is introduced to solve problems where it is not computationally feasible or economically desirable to compute the optimal solution. Its flexibility, combined with parallel and faster processing of distributed artificial intelligence methods, allows the improvement of the centralized technique of scheduling. Indeed, scheduling is distributed among agents while negotiation is performed to solve impasses between local schedules. This negotiation is based on flexing local schedules by discarding the least important reasoning levels to borrow resources. The progressive structure of agents facilitates the solving of impasses by discarding the deepest levels such that rescheduling is avoided. A system is designed where each progressive reasoning agent is completely autonomous and then it is up to locally build its schedule and to co-ordinate it with the other. This approach is an important application of the contract-net technique to the scheduling of progressive reasoning agents. This approach is dedicated to the distributed station resource management application.

Controlling resource-bounded systems not only involves taking decisions about planning and scheduling reasoning components to achieve time-constrained goals, but also about how to monitor the progress of these components. We propose an extended closed-loop planning, scheduling and execution. This extended closed-loop allows one to address the following limitations: (1) dynamic and time-constrained environments, (2) uncertainty regarding the duration of reasoning components and (3) tolerance to execution failure. The interactions in the extended closed-loop allow one: first to revise the current schedule when deviations from a predetermined schedule occur during execution, second to update continuously the set of goals on which the control focuses its decision and third how this set of goals is updated when an execution failure occurs. We discuss these issues in a progressive reasoning system implemented and applied to a railway control application where real-time (dynamic and time-constrained) situations occur.

Controlling complex real-world systems that involve hard deadlines using artificial intelligence (AI) must deal with the difficulty which stems from their unpredictable aspects. We present an intelligent control strategy based on a progressive scheduling algorithm where the duration of tasks is uncertain. This control strategy can meet deadlines while still using unpredictable AI techniques. This control strategy is based on a flexible scheduling algorithm to guarantee or trade-off timeliness and the quality of the solution. The performance of this algorithm is compared to other progressive scheduling approaches where the duration is assumed known.

The problem of producing timely responses when faced with deadlines is an important issue for real-time systems. To deal with this problem different kinds of scheduling algorithms have been developed within the real-time community. Unfortunately, these approaches fail when applied to knowledge based systems, mainly because AI techniques rely on time-consuming algorithms with unpredictable, or highly variable performances. To face this problem researchers in AI have introduced deliberative techniques that enable to adapt the way a task is working in function of the available time. For this purpose approximation algorithms of two kinds have been developed: iterative refinement and multiple methods. The model we propose in this paper, belongs to iterative refinement methods. The main advantage of our approach is the capability of designing iterative refinement methods using a general rule language.>