Inverse reinforcement learning (IRL) techniques (Ng and Russell, 2000) provide a foundation for detecting abnormal agent behavior and predicting agent intent through estimating its reward function. Unfortunately, IRL algorithms suffer from the large dimensionality of the reward function space. Meanwhile, most applications that can benefit from an IRL-based approach to assessing agent intent, involve interaction with an analyst or domain expert. This paper proposes a procedure for scaling up IRL by eliciting good IRL basis functions from the domain expert. Further, we propose a new paradigm for modeling limited rationality. Unlike traditional models of limited rationality that assume an agent making stochastic choices with the value function being treated as if it is known, we propose that observed irrational behavior is actually due to uncertainty about the cost of future actions. This treatment normally leads to a POMDP formulation which is unnecessarily complicated, and we show that adding a simple noise term to the value function approximation accomplishes the same at a much smaller cost.

In this paper we present a neural-symbolic system for monitoring traces of observations in sofware systems. To this end, we define an algorithm that translates a RuleR rule-based monitoring system (RS) into a rule-based neural network system (RNNS). We then show how the RNNS can perform trace monitoring effectively and analyze its performance, reporting promising preliminary results. Finally, we discuss how network learning could be used within RNNS to embed the system into a framework for iterative verification and model adaptation. It is hoped that a tight integration of verification and adaptation within the neural-symbolic approach will help support the development of self-adapting, self-healing systems.

For the problem of moving a set of agents on a connected graphto agent-specific goal locations, free of collisions, we propose a multiflow based integer linear programming (ILP) model that finds a time optimal solution. The resulting algorithm from our ILP model is complete and guarantees to yield true optimal solutions. Focusing on the time optimal formulation, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. The computational results confirm the effectiveness of our method.

Problems that require multiple agents to follow non-interfering paths from their current states to their respective goal states are called multi-agent pathfinding problems (MAPFs). In previous work, we presented Independence Detection (ID), an algorithm for breaking a large MAPF problem into smaller problems that can be solved independently. Independence Detection is complete and can be used in combination with both optimal and approximation algorithms. This paper serves as an introduction to Independence Detection and aims to clarify its details.

Collision avoidance and multi-agent navigation is an important component of modern video games. Recent developments in commodity hardware, in particular the utilization of multi-core and many-core architectures in personal computers and consoles are allowing large numbers of virtual agents to be incorporated into game levels in increasing numbers. We present the hybrid reciprocal velocity obstacle and optimal reciprocal collision avoidance methods for reciprocal collision avoidance and navigation in video games and described their implementations in C++ as HRVO Library and RVO2 Library. The libraries can efficiently simulate groups of twenty-five to one thousand virtual agents in dense conditions and around moving and static obstacles.

In the multi agent path finding problem (MAPF) paths shouldbe found for several agents, each with a different start andgoal position such that agents do not collide. Previous optimalsolvers applied global A*-based searches. We presenta new search algorithm called Conflict Based Search (CBS).CBS is a two-level algorithm. At the high level, a search isperformed on a tree based on conflicts between agents. At thelow level, a search is performed only for a single agent at atime. In many cases this reformulation enables CBS to examinefewer states than A* while still maintaining optimality.We analyze CBS and show its benefits and drawbacks. Experimentalresults on various problems shows a speedup ofup to a full order of magnitude over previous approaches.

Motivated by efficient algorithms for solving combina- torial and discrete instances of the multi-agent pathfinding problem, this report investigates ways to utilize such solutions to solve similar problems in the continuous domain. While a simple discretization of the space which allows the direct application of combinatorial algorithms seems like a straightforward solution, there are additional constraints that such a discretization needs to satisfy in order to be able to provide some form of completeness guarantees in general configuration spaces. This report reviews ideas on how to utilize combinatorial algorithms to solve continuous multi-agent pathfinding problems. It aims to collect feedback from the community regarding the importance and the complexity of this challenge, as well as the appropriateness of the solutions considered here.

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.

Multi-agent path finding has been proven to be a PSPACE-hard problem. Generating such a centralised multi-agent plan can be avoided, by allowing agents to plan their paths separately. However, this results in an increased number of collisions and agents must re- plan frequently. In this paper we present a framework for multi-agent path planning, which allows agents to plan independently and solve conflicts locally when they occur. The framework is a generalisation of the CQ-learning algorithm which learns sparse interactions between agents in a multi-agent reinforcement learning setting

In this paper we present a formal approach to reciprocal collision avoidance for multiple mobile robots sharing a common 2-D or 3-D workspace whose dynamics are subject to linear differential constraints. Our approach defines a protocol for robots to select their control input independently (i.e. without coordination with other robots) while guaranteeing collision-free motion for all robots, assuming the robots can perfectly observe each other's state. To this end, we use the concept of LQR-Obstacles that define sets of forbidden control inputs that lead a robot to collision with obstacles, and extend it for reciprocal collision avoidance among multiple robots. We implemented and tested our approach in 3-D simulation environments for reciprocal collision avoidance of quadrotorhelicopters, which have complex dynamics in 16-D state spaces. Our results suggest that our approach avoids collisions among over a hundred quadrotors in tight workspaces at real-time computation rates.