CBS is a state-of-the-art MAPF algorithm whose performance has been enhanced over the years by the introduction of heuristics that focus the search and reasoning techniques that identify specific types of conflicts that can be resolved faster. To further improve the efficiency of CBS, we present a novel idea based on constraint-reasoning techniques that merges similar high-level nodes close to the root of the constraint tree while preserving CBS' optimality. As a result, some of CBS' duplicate work that occurs when expanding similar high-level nodes is avoided. Our first experimental results using a simple CBS variant (ICBS-h) show a significant reduction in the number of expanded high-level nodes on average.

On an assigned graph, the problem of Multi-Agent Pathfinding (MAPF) consists in finding paths for multiple agents, avoiding collisions. Finding the minimum-length solution is known to be NP-hard, and computation times grows exponentially with the number of agents. However, in industrial applications, it is important to find feasible, suboptimal solutions, in a time that grows polynomially with the number of agents. Such algorithms exist for undirected and biconnected directed graphs. Our main contribution is to generalize these algorithms to the more general case of strongly connected directed graphs. In particular, we describe a procedure that checks the problem feasibility in linear time with respect to the number of vertices n , and we find a necessary and sufficient condition for feasibility of any MAPF instance. Moreover, we present an algorithm (diSC) that provides a feasible solution of length O ( k n 2 c ) , where k is the number of agents and c the maximum length of the corridors of the graph.

Research on multi-agent pathfinding (MAPF) has recently shifted towards problem variants that are closer to actual applications. Such variants often include the assignment of multiple goals to agents. To solve them, researchers have extended the Conflict Based Search (CBS) algorithm to multiple goals. This extension might look straightforward at first sight but it is tricky and this has already led to the development of algorithms that despite claiming to be optimal, return suboptimal solutions for some MAPF instances. In this paper, we provide a detailed analysis of the issue to raise awareness among the search community so that this mistake will not be perpetuated. Furthermore, a first evaluation against an optimal implementation is conducted which shows why this issue might have been difficult to spot. In only one of the randomly generated instances, the suboptimal behavior emerged.

The pebble motion on trees (PMT) problem consists in finding a feasible sequence of moves that repositions a set of pebbles to assigned target vertices. This problem has been widely studied because, in many cases, the more general Multi-Agent path finding (MAPF) problem on graphs can be reduced to PMT. We propose a simple and easy to implement procedure, which finds solutions of length O(|P|nc + n2), where n is the number of nodes, P is the set of pebbles, and c the maximum length of corridors in the tree. This complexity result is more detailed than the current best known result O(n3), which is equal to our result in the worst case, but does not capture the dependency on c and |P|.

We introduce the multi-agent transportation (MAT) problem, where agents have to transport containers from their starting positions to their designated goal positions. Movement takes place in a common environment where collisions between agents and between containers must be avoided. In contrast to other frameworks such as multi-agent pathfinding (MAPF) or multi-agent pickup and delivery (MAPD), the agents are allowed to separate from the containers at any time, which can reduce the makespan and also allows for plans in scenarios that are unsolvable otherwise. We present a complexity analysis establishing the problem's NP-completeness and show how the problem can be reduced to a sequence of SAT problems when optimizing for makespan. A MAT solver is empirically evaluated with regard to varying input characteristics and movement constraints and compared to a MAPD solver that utilizes conflict-based search (CBS).

State constraints in AI Planning globally restrict the legal environment states. Standard planning languages make closed-domain and closed-world assumptions. Here we address open-world state constraints formalized by planning over a description logic (DL) ontology. Previously, this combination of DL and planning has been investigated for the light-weight DL DL-Lite. Here we propose a novel compilation scheme into standard PDDL with derived predicates, which applies to more expressive DLs and is based on the rewritability of DL queries into Datalog with stratified negation. We also provide a new rewritability result for the DL Horn-ALCHOIQ, which allows us to apply our compilation scheme to quite expressive ontologies. In contrast, we show that in the slight extension Horn-SROIQ no such compilation is possible unless the weak exponential hierarchy collapses. Finally, we show that our approach can outperform previous work on existing benchmarks for planning with DL ontologies, and is feasible on new benchmarks taking advantage of more expressive ontologies.

The objective of top-k planning is to determine a set of k different plans with lowest cost for a given planning task. In practice, such a set of best plans can be preferred to a single best plan generated by ordinary optimal planners, as it allows the user to choose between different alternatives and thus take into account preferences that may be difficult to model. In this paper we show that, in general, the decision problem version of top-k planning is PSPACE-complete, as is the decision problem version of ordinary classical planning. This does not hold for polynomially bounded plans for which the decision problem turns out to be PP-hard, while the ordinary case is NP-hard. We present a novel approach to top-k planning, called sym-k, which is based on symbolic search, and prove that sym-k is sound and complete. Our empirical analysis shows that sym-k exceeds the current state of the art for both small and large k.

Epistemic planning has been employed as a means to achieve implicit coordination in cooperative multi-agent systems where world knowledge is distributed between the agents, and agents plan and act individually. However, recent work has shown that even if all agents act with respect to plans that they consider optimal from their own subjective perspective, infinite executions can occur. In this paper, we analyze the idea of using a single token that can be passed around between the agents and which is used as a prerequisite for acting. We show that introducing such a token to any planning task will prevent the existence of infinite executions. We furthermore analyze the conditions under which solutions to a planning task are preserved under our tokenization.

Research in classical planning so far was mainly concerned with generating a satisficing or an optimal plan. However, if such systems are used to make decisions that are relevant to humans, one should also consider the ethical consequences generated plans can have. We address this challenge by analyzing in how far it is possible to generalize existing approaches of machine ethics to automatic planning systems. Traditionally, ethical principles are formulated in an actionbased manner, allowing to judge the execution of one action. We show how such a judgment can be generalized to plans. Further, we study the computational complexity of making ethical judgment about plans.

In multi-agent path finding, it is usually assumed that planning is performed centrally and that the destinations of the agents are common knowledge. We will drop both assumptions and analyze under which conditions it can be guaranteed that the agents reach their respective destinations using implicitly coordinated plans without communication.

We present a novel search scheme for privacy-preserving multi-agent planning. Inspired by UCT search, the scheme is based on growing an asynchronous search tree by running repeated trials through the tree. We describe key differences to classical multi-agent forward search, discuss theoretical properties of the presented approach, and evaluate it based on benchmarks from the CoDMAP competition. As a secondary contribution, we describe a technique that extends the regular search approach by small explorative trials which are performed subsequent to each node expansion. We show that this technique significantly increases the number of problems solved for all algorithms considered, including MAFS.

In multi-agent path finding (MAPF), it is usually assumed that planning is performed centrally and that the destinations of the agents are common knowledge. We will drop both assumptions and analyze under which conditions it can be guaranteed that the agents reach their respective destinations using implicitly coordinated plans without communication. Furthermore, we will analyze what the computational costs associated with such a coordination regime are. As it turns out, guarantees can be given assuming that the agents are of a certain type. However, the implied computational costs are quite severe. In the distributed setting, we either have to solve a sequence of NP-complete problems or have to tolerate exponentially longer executions. In the setting with destination uncertainty, bounded plan existence becomes PSPACE-complete. This clearly demonstrates the value of communicating about plans before execution starts.

When planning for tasks that feature both state-dependent action costs and conditional effects using relaxation heuristics, the following problem appears: handling costs and effects separately leads to worse-than-necessary heuristic values, since we may get the more useful effect at the lower cost by choosing different values of a relaxed variable when determining relaxed costs and relaxed active effects. In this paper, we show how this issue can be avoided by representing state-dependent costs and conditional effects uniformly, both as edge-valued multi-valued decision diagrams (EVMDDs) over different sets of edge values, and then working with their product diagram. We develop a theory of EVMDDs that is general enough to encompass state-dependent action costs, conditional effects, and even their combination.We define relaxed effect semantics in the presence of state-dependent action costs and conditional effects, and describe how this semantics can be efficiently computed using product EVMDDs. This will form the foundation for informative relaxation heuristics in the setting with state-dependent costs and conditional effects combined.

Several different frameworks have been proposed to model and reason about knowledge in dynamic multi-agent settings, among them the logic-programming-based game description language GDL-III, and dynamic epistemic logic (DEL), based on possible-worlds semantics. GDL-III and DEL have complementary strengths and weaknesses in terms of ease of modeling and simplicity of semantics. In this paper, we formally study the expressiveness of GDL-III vs. DEL. We clarify the commonalities and differences between those languages, demonstrate how to bridge the differences where possible, and identify large fragments of GDL-III and DEL that are equivalent in the sense that they can be used to encode games or planning tasks that admit the same legal action sequences. We prove the latter by providing compilations between those fragments of GDL-III and DEL.

Increasing the accessibility of autonomous robots also for inexperienced users requires user-friendly and high-level control opportunities of robotic systems. While automated planning is able to decompose a complex task into a sequence of steps which reaches an intended goal, it is difficult to formulate such a goal without knowing the internals of the planning system and the exact capabilities of the robot. This becomes even more important in dynamic environments in which manipulable objects are subject to change. In this paper, we present an adaptive control interface which allows users to specify goals based on an internal world model by incrementally building referring expressions to the objects in the world. We consider fetch-and-carry tasks and automatically deduce potential high-level goals from the world model to make them available to the user. Based on its perceptions our system can react to changes in the environment by adapting the goal formulation within the domain-independent planning system.

To address the requirement for autonomous moral decision making, we introduce a software library for modeling hybrid ethical reasoning agents (short: HERA). The goal of the HERA project is to provide theoretically well-founded and practically usable logic-based machine ethics tools for implementation in robots. The novelty is that HERA implements multiple ethical principles like utilitarianism, the principle of double effect, and a Pareto-inspired principle. These principles can be used to automatically assess moral situations represented in a format we call causal agency models. We discuss how to model moral situations using our approach, and how it can cope with uncertainty about moral values. Finally, we briefly outline the architecture of our robot IMMANUEL, which implements HERA and is able to explain ethical decisions to humans.

In current approaches to combined task and motion planning, usually symbolic planning and sampling based motion-planning are integrated. One problem is here to come up with good samples. We address the problem of identifying useful poses for a robot close to working surfaces such as tables or shelves. Our approach is based on reachability inversion which answers the question: where should the robot be located in order to reach a certain object? We extend the concept from point-based objects to flat polygonal surfaces in order to enable the robot to have a a good grasping position for many objects. Our approach allows to quickly sample multiple distinct poses for the robot from an prior computed distribution. Further we show how sampling from an inverse reachability distribution can be integrated into a CTAMP system.

We adapt the relaxation heuristics hmax, hadd and hFF to interval based numeric relaxation frameworks, combining them with two different relaxation techniques and with two different search techniques. In contrast to previous approaches, the heuristics presented here are not limited to a subset of numeric planning and support action costs.

Localization in dynamic environments is still a challenging problem in robotics - especially if rapid and large changes occur irregularly. Inspired by SLAM algorithms, our Bayesian approach to this so-called dynamic localization problem divides it into a localization problem and a mapping problem, respectively. To tackle the localization problem we use a particle filter, coupled with a distance filter and a scan matching method, which achieves a more robust localization against dynamic obstacles. For the mapping problem we use an extended sensor model which results in an effective and precise map update effect. We compare our approach against other localization methods and evaluate the impact the map update effect has on the localization in dynamic environments.

We present a novel search scheme for privacy-preserving multi-agent planning, inspired by UCT search. We compare the presented approach to classical multi-agent forward search and evaluate it based on benchmarks from the CoDMAP competition.

Planning-based methods to guide switched hybrid systems from an initial state into a desired goal region opens an interesting field for control. The idea of the Domain Predictive Control (DPC) approach is to generate input signals affecting both the numerical states and the modes of the system by stringing together atomic actions to a logically consistent plan. However, the existing DPC approach is restricted in the sense that a discrete and pre-defined input signal is required for each action. In this paper, we extend the approach to deal with symbolic states. This allows for the propagation of reachable regions of the state space emerging from actions with inputs that can be arbitrarily chosen within specified input bounds. This symbolic extension enables the applicability of DPC to systems with bounded inputs sets and increases its robustness due to the implicitly reduced search space. Moreover, precise numeric goal states instead of goal regions become reachable.

This paper describes the results of a qualitative analysis of questionnaire data collected during a public exhibition of our robotic tele-presence system. In Summer 2013 the mildly humanized robot DARYL could be tried out by the general public during our University's science fair in the city center. People were given the chance to communicate through the robot with their peers and to perceive the world through the "eyes" and "ears" of the robot by means of a head-mounted display with attached headphones. An operator's voice was instantaneously transmitted to the robot's location and his or her head movements were tracked to enable direct, intuitive control of the robot's head movements. Twenty-seven people were interviewed in a structured way about their impressions and opinions after having either operated or interacted with the tele-operated robot. A careful analysis of the acquired data reveals a rather positive evaluation of the tele-presence system and interesting opinions about suitable application areas. These findings may guide designers of robotic tele-presence systems, a research area of increasing popularity.

This paper introduces MARCO, a hybrid, chess playing agent equipped with a custom-built robotic arm and an emotionally expressive, virtual face presented on a small, servo-controlled display. MARCO was built to investigate the hypothesis that hybrid systems capable of displaying emotions make playing chess more personal and enjoyable. In addition, it is our aim to realize emotional contagion between man and machine in that the agent has the power to influence the human player on an emotional level and vice versa. The hardware components consist of eight Dynamixel servos, an Arduino-based control board, a 5.6 inch display, and a DGT chessboard. The software components run concurrently as separate processes. The main components are the virtual agent framework MARC, the WASABI Affect Simulation architecture, and the TSCP chess engine.

We present MARCO, a hybrid, chess playing agent equipped with a custom-built robotic arm and a virtual agent's face displaying emotions. MARCO was built to investigate the hypothesis that hybrid agents capable of displaying emotions make playing chess more personal and enjoyable. In addition, we aim to explore means of achieving emotional contagion between man and machine.

Autonomous robot teams that simultaneously dispatch transportation tasks are playing a more and more important role in the industry. In this paper we consider the multi-robot motion planning problem in large robot teams and present a decoupled approach by combining decentralized path planning methods and swarm technologies. Instead of a central coordination, a proper behavior which is directly selected according to the context is used by the robot to keep cooperating with others and to resolve path collisions. We show experimentally that the quality of solutions and the scalability of our method are significantly better than those of conventional decoupled path planning methods. Furthermore, compared to conventional swarm approaches, our method can be widely applied in large-scale environments.

The generation of route descriptions is a fundamental task of navigation systems. A particular problem in this context is to identify routes that can easily be described and processed by users. In this work, we present a framework for representing route n

The problem of autonomously exploring an environment with a team of robots received considerable attention in the past. However, there are relatively few approaches to coordinate teams of robots that are able to deploy and retrieve other robots. Efficiently coordinating the exploration with such marsupial robots requires advanced planning mechanisms that are able to consider symbolic deployment and retrieval actions. In this paper, we propose a novel approach for coordinating the exploration with marsupial robot teams. Our method integrates a temporal symbolic planner that explicitly considers deployment and retrieval actions with a traditional cost-based assignment procedure. Our approach has been implemented and evaluated in several simulated environments and with varying team sizes. The results demonstrate that our proposed method is able to coordinate marsupial teams of robots to efficiently explore unknown environments.

To coordinate a team of robots for exploration is a challenging problem, particularly in large areas as for example the devastated area after a disaster. This problem can generally be decomposed into task assignment and multi-robot path planning. In this paper, we address both problems jointly. This is possible because we reduce significantly the size of the search space by utilizing RFID tags as coordination points. The exploration approach consists of two parts: a stand-alone distributed local search and a global monitoring process which can be used to restart the local search in more convenient locations. Our results show that the local exploration works for large robot teams, particularly if there are limited computational resources. Experiments with the global approach showed that the number of conflicts can be reduced, and that the global coordination mechanism increases significantly the explored area.

The ability to reason in space is crucial for agents in order to make informed decisions. Current high-level qualitative approaches to spatial reasoning have serious deficiencies in not reflecting the hierarchical nature of spatial data and human spatial cognition. This article proposes a framework for hierarchical representation and reasoning about topological information, where a continuous model of space is approximated by a collection of discrete sub-models, and spatial information is hierarchically represented in discrete sub-models in a rough set manner. The work is based on the Generalized Region Connection Calculus theory, where continuous and discrete models of space are coped in a unified way. Reasoning issues such as determining the mereological (part-whole) relations between two rough regions are also discussed. Moreover, we consider an important problem that is closely related to map generalization in cartography and Geographical Information Science. Given a spatial configuration at a finer level, we show how to construct a configuration at a coarser level while preserving the mereological relations.

Robot search and rescue is a time critical task, i.e. a large terrain has to be explored by multiple robots within a short amount of time. The efficiency of exploration depends mainly on the coordination between the robots and hence on the reliability of communication, which considerably suffers under the hostile conditions encountered after a disaster. Furthermore, rescue robots have to generate a map of the environment which has to be sufficiently accurate for reporting the locations of victims to human task forces. Basically, the robots have to solve autonomously in real-time the problem of simultaneous localization and mapping (SLAM). This paper proposes a novel method for real-time exploration and SLAM based on RFID tags that are autonomously distributed in the environment. We utilized the algorithm of Lu and Milios for calculating globally consistent maps from detected RFID tags. Furthermore we show how RFID tags can be used for coordinating the exploration of multiple robots. Results from experiments conducted in the simulation and on a robot show that our approach allows the computationally efficient construction of a map within harsh environments, and coordinated exploration of a team of robots

If multiple cleaning robots are used to cooperatively clean a larger room, e.g. an airport, the room must be partitioned among the robots. The paper describes a dynamic and decentralized method to partition a certain area among multiple robots. The area is divided into polygons, which are allocated by the robots. After a robot has been allocated a certain polygon, it is responsible for cleaning the polygon. The method described in the paper does not need any global synchronization and does not require a global communication network.

Robotic soccer is a challenging research domain because many different research areas have to be addressed in order to create a successful team of robot players. The paper presents the CS Freiburg team, the winner in the middle-size league at RoboCup 1998, 2000, and 2001. The paper focuses on multiagent coordination for both perception and action. The contributions of the paper are new methods for tracking ball and players observed by multiple robots, team coordination methods for strategic team formation and dynamic role assignment; a rich set of basic skills allowing robots to respond to a large range of situations in an appropriate way, and an action-selection method based on behavior networks, as well as a method to learn the skills and their selection. As demonstrated by evaluations of the different methods and by the success of the team, these methods permit the creation of a multirobot group which is able to play soccer successfully. In addition, the developed methods promise to advance the state of the art in the multirobot field.

This work presents methods for tracking objects from noisy and unreliable data taken by a team of robots. We develop a multi-object tracking algorithm based on Kalman filtering and a single-object tracking method involving a combination of Kalman filtering and Markov localization for outlier detection. We apply these methods in the context of robot soccer for robots participating in the RoboCup middle-size league and compare them to a simple averaging method. Results including situations from real competition games are presented.

This paper describes a method for coordinating the independently planned trajectories of multiple mobile robots to avoid collisions and deadlocks among them. Whenever the distance between two robots drops below a certain value, they exchange information about their planned trajectories and determine whether they are in danger of a collision. If a possible collision is detected, they monitor their movements and, if necessary, insert idle times between certain segments of their trajectories in order to avoid the collision. Deadlocks among two or more robots occur if a number of robots block each other in a way such that none of them is able to continue along its trajectory without causing a collision. These deadlocks are reliably detected. After a deadlock is detected, the trajectory planners of each of the involved robots are successively asked to plan an alternative trajectory until the deadlock is resolved We use a combination of three fully distributed algorithms to reliably solve the task They do not use any global synchronization and do not interfere with each other.

We describe and evaluate the algorithmic techniques that are used in the FF planning system. Like the HSP system, FF relies on forward state space search, using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP's heuristic, our method does not assume facts to be independent. We introduce a novel search strategy that combines hill-climbing with systematic search, and we show how other powerful heuristic information can be extracted and used to prune the search space. FF was the most successful automatic planner at the recent AIPS-2000 planning competition. We review the results of the competition, give data for other benchmark domains, and investigate the reasons for the runtime performance of FF compared to HSP.

The theoretical properties of qualitative spatial reasoning in the RCC8 framework have been analyzed extensively. However, no empirical investigation has been made yet. Our experiments show that the adaption of the algorithms used for qualitative temporal reasoning can solve large RCC8 instances, even if they are in the phase transition region -- provided that one uses the maximal tractable subsets of RCC8 that have been identified by us. In particular, we demonstrate that the orthogonal combination of heuristic methods is successful in solving almost all apparently hard instances in the phase transition region up to a certain size in reasonable time.

The recent approaches of extending the GRAPHPLAN algorithm to handle more expressive planning formalisms raise the question of what the formal meaning of ``expressive power'' is. We formalize the intuition that expressive power is a measure of how concisely planning domains and plans can be expressed in a particular formalism by introducing the notion of ``compilation schemes'' between planning formalisms. Using this notion, we analyze the expressiveness of a large family of propositional planning formalisms, ranging from basic STRIPS to a formalism with conditional effects, partial state specifications, and propositional formulae in the preconditions. One of the results is that conditional effects cannot be compiled away if plan size should grow only linearly but can be compiled away if we allow for polynomial growth of the resulting plans. This result confirms that the recently proposed extensions to the GRAPHPLAN algorithm concerning conditional effects are optimal with respect to the ``compilability'' framework. Another result is that general propositional formulae cannot be compiled into conditional effects if the plan size should be preserved linearly. This implies that allowing general propositional formulae in preconditions and effect conditions adds another level of difficulty in generating a plan.

Self-localization is important in almost all robotic tasks. For playing an aesthetic and effective game of robotic soccer, self-localization is a necessary prerequisite. When we designed our robotic soccer team for RoboCup'98, it turned out that all existing approaches did not meet our requirements of being fast, accurate, and robust. For this reason, we developed a new method, which is presented and analyzed in the paper We additionally present experimental evidence that our method outperforms other methods in the RoboCup environment.

We have previously reported a number of tractable planning problems defined in the SAS+ formalism. This article complements these results by providing a complete map over the complexity of SAS+ planning under all combinations of the previously considered restrictions. We analyze the complexity of both finding a minimal plan and finding any plan. In contrast to other complexity surveys of planning, we study not only the complexity of the decision problems but also the complexity of the generation problems. We prove that the SAS+‐PUS problem is the maximal tractable problem under the restrictions we have considered if we want to generate minimal plans. If we are satisfied with any plan, then we can generalize further to the SAS+‐US problem, which we prove to be the maximal tractable problem in this case.

We introduce a new subclass of Allen's interval algebra we call “ORD-Horn subclass,” which is a strict superset of the “pointisable subclass.” We prove that reasoning in the ORD-Horn subclass is a polynomial-time problem and show that the path-consistency method is sufficient for deciding satisfiability. Further, using an extensive machine-generated case analysis, we show that the ORD-Horn subclass is a maximal tractable subclass of the full algebra (assuming P ≠ NP). In fact, it is the unique greatest tractable subclass amongst the subclasses that contain all basic relations.