Search

We address the problem of evacuation from the heuristic search perspective combined with agent-based modeling (ABM). The evacuation problem is modeled as a navigation of multiple agents in a known environment. The environment is divided into a danger and a safe zone while the task of agents is to move from the danger zone to the safe zone in a collision-free manner. Unlike previous approaches that model the environment as a discrete graph with agents placed in its vertices, at most one agent per vertex, our approach adopts various continuous aspects such as a grid-based embedding of the environment into 2D space and continuous line of sight of agents. In addition to this, we adopt hierarchical structure of our multi-agent system in which so called leading agents are more informed and are capable of performing multi-agent pathfinding (MAPF) via centralized algorithms like conflict-based search (CBS) while so called following agents with limited knowledge about other agents are modeled using simple local rules. Our experimental evaluation indicates that suggested hierarchical modeling approach can serve as a tool for studying the progress and the efficiency of evacuation processes in different environments.

Classical planning is a task of finding a sequence of actions that achieve a given goal. One of many approaches to classical planning is compilation into propositional satisfiability (SAT). In this work, we propose a new method that uses lazy compilation into SAT. Different from the standard compilation method, lazy compilation constructs the target propositional formula step by step while the SAT solver is consulted at each step and refinements of the formula are suggested according to SAT solver's answers. The performed experiments pointed out that lazy compilation has the potential to improve the performance of the planners.

Multi-agent path finding (MAPF) represents a task of finding non-colliding paths for agents via which they can navigate from their initial positions to specified goal positions. Contemporary optimal solving algorithms include dedicated search-based methods, that solve the problem directly, and compilation-based algorithms that reduce MAPF to a different formalism for which an efficient solver exists. In this paper, we enhance the existing Boolean satisfiability-based (SAT) algorithm for MAPF via using sparse decision diagrams representing the set of candidate paths for each agent, from which the target Boolean encoding is derived, considering more promising paths before the less promising ones are taken into account. Suggested sparse diagrams lead to a smaller target Boolean formulae that can be constructed and solved faster while optimality guarantees of the approach are kept. Specifically, considering the candidate paths sparsely instead of considering them all makes the SAT-based approach more competitive for MAPF on large maps.

In the multi-agent path finding problem (MAPF) we are given a set of agents each with respective start and goal positions. The task is to find paths for all agents while avoiding collisions, aiming to minimize a given objective function. Many MAPF solvers were introduced in the past decade for optimizing two specific objective functions: sum-of-costs and makespan. Two prominent categories of solvers can be distinguished: search-based solvers and compilation-based solvers. Search-based solvers were developed and tested for the sum-of-costs objective, while the most prominent compilation-based solvers that are built around Boolean satisfiability (SAT) were designed for the makespan objective. Very little is known on the performance and relevance of solvers from the compilation-based approach on the sum-of-costs objective. In this paper, we start to close the gap between these cost functions in the compilation-based approach. Our main contribution is a new SAT-based MAPF solver called MDD-SAT, that is directly aimed to optimally solve the MAPF problem under the sum-of-costs objective function. Using both a lower bound on the sum-of-costs and an upper bound on the makespan, MDD-SAT is able to generate a reasonable number of Boolean variables in our SAT encoding. We then further improve the encoding by borrowing ideas from ICTS, a search-based solver. In addition, we show that concepts applicable in search-based solvers like ICTS and ICBS are applicable in the SAT-based approach as well. Specifically, we integrate independence detection, a generic technique for decomposing an MAPF instance into independent subproblems, into our SAT-based approach, and we design a relaxation of our optimal SAT-based solver that results in a bounded suboptimal SAT-based solver. Experimental evaluation on several domains shows that there are many scenarios where our SAT-based methods outperform state-of-the-art sum-of-costs search-based solvers, such as variants of the ICTS and ICBS algorithms.

In multi-agent path finding (MAPF) the task is to find nonconflicting paths for multiple agents. In this paper we focus on finding suboptimal solutions for MAPF for the sum-of-costs variant. Recently, a SAT-based approached was developed to solve this problem and proved beneficial in many cases when compared to other search-based solvers. In this paper, we present SAT-based unbounded- and bounded-suboptimal algorithms and compare them to relevant algorithms. Experimental results show that in many case the SAT-based solver significantly outperforms the search-based solvers.

Multi-agent path finding (MAPF) attracts considerable attention in artificial intelligence community. The task in the standard MAPF is to find discrete paths through which agents can navigate from their starting positions to individual goal positions. The combination of two additional requirements makes the problem computationally challenging: agents must not collide with each other and the paths must be optimal with respect to some objective. Two major approaches to optimal MAPF solving include dedicated search-based methods, and compilation-based methods that reduce a MAPF instance to an instance in a different formalism, for which an efficient solver exists. In this survey, we summarize major compilation-based solvers for MAPF using CSP, SAT, and MILP formalisms. We explain the core ideas of the solvers in a simplified and unified way while preserving the merit making them more accessible for a wider audience.

The task in multi-agent path finding (MAPF) is to find paths through which agents can navigate from their starting positions to given individual goal positions. The combination of two additional requirements makes the problem challenging: (i) agents must not collide with each other and (ii) the paths must be optimal with respect to some objective. We summarize and compare main ideas of contemporary compilation-based solvers for MAPF using MIP and SAT formalisms.

Multi-agent path finding with continuous movements and time (denoted MAPF-R) is addressed. The task is to navigate agents that move smoothly between predefined positions to their individual goals so that they do not collide. Recently a novel solving approach for obtaining makespan optimal solutions called SMT-CCBS based on satisfiability modulo theories (SMT) has been introduced. We extend the approach further towards the sum-of-costs objective which is a more challenging case in the yes/no SMT environment due to more complex calculation of the objective.

We present ESO-MAPF, a research and educational platform for experimenting with multi-agent path finding (MAPF). ESO-MAPF focuses on demonstrating the planning-acting chain in the MAPF domain. MAPF is the task of finding collision free paths for agents from their starting positions to given individual goals. The standard MAPF uses the abstraction where agents move in an undirected graph via traversing its edges in discrete steps. The discrete abstraction simplifies the planning phase however resulting discrete plans often need to be executed in the real continuous environment. ESO-MAPF shows how to bridge discrete planning and the acting phase in which the resulting plans are executed on physical robots. We simulate centralized plans on a group of OZOBOT Evo robots using their reflex functionalities and outputs on the surface of the screen that serves as the environment. Various problems arising along the planning-acting chain are illustrated to emphasize the educational point of view.

Mutex propagation is a form of efficient constraint propagation popularly used in AI planning to tightly approximate the reachable states from a given state. We utilize this idea in the context of Multi-Agent Path Finding (MAPF). When adapted to MAPF, mutex propagation provides stronger constraints for conflict resolution in Conflict-Based Search (CBS), a popular optimal MAPF algorithm, and provides it with the ability to identify and reason with symmetries in MAPF. While existing work identifies a limited form of symmetries using rectangle reasoning and requires the manual design of symmetry-breaking constraints, mutex propagation is more general and allows for the automated design of symmetry-breaking constraints. Our experimental results show that CBS with mutex propagation is capable of outperforming CBSH with rectangle reasoning, a state-of-the-art variant of CBS, with respect to runtime and success rate.

We address the design of heuristics for near-optimal solving of the (N2–1)-puzzle using the A* search algorithm in this paper. The A* search algorithm explores configurations of the puzzle in the order determined by a heuristic that tries to estimate the minimum number of moves needed to reach the goal from the given configuration. To guarantee finding an optimal solution, the A* algorithm requires heuristics that estimate the number of moves from below. Common heuristics for the (N2–1)-puzzle often underestimate the true number of moves greatly in order to meet the admissibility requirement. The worse the estimation is the more configurations the search algorithm needs to explore. We therefore relax from the admissibility requirement and design a novel heuristic that tries estimating the minimum number of moves remaining as precisely as possible while overestimation of the true distance is permitted. Our heuristic called ANN-distance is based on a deep artificial neural network (ANN). We experimentally show that with a well trained ANN-distance heuristic, whose inputs are just the positions of the tiles, we are able to achieve better accuracy of estimation than with conventional heuristics such as those derived from the Manhattan distance or pattern database heuristics. Though we cannot guarantee admissibility of ANN-distance due to possible overestimation of the true number of moves, an experimental evaluation on random 15-puzzles shows that in most cases the ANN-distance calculates the true minimum distance from the goal or an estimation that is very close to the true distance. Consequently, A* search with the ANN-distance heuristic usually finds an optimal solution or a solution that is very close to the optimum. Moreover, the underlying neural network in ANN-distance consumes much less memory than a comparable pattern database. We also show that a deep artificial neural network can be more powerful than a shallow artificial neural network, and also trained our heuristic to prefer underestimating the optimal solution cost, which pushed the solutions towards better optimality.

Multi-agent path finding (MAPF) is the problem of planning a set of non-colliding paths for a set of agents so that each agent reaches its individual goal location following its path. A mutex from classical planning is a constraint forbidding a pair of facts to be both true or a pair of actions to be executed simultaneously. In the context of MAPF, mutexes are used to rule out the simultaneous occurrence of a pair of agents in a pair of locations, which can prune the search space. Previously mutex propagation had been integrated into conflict-based search (CBS), a major search-based approach for solving MAPF optimally. In this paper, we introduce mutex propagation into the compilation-based (SAT-based) solver MDD-SAT, an alternative to search-based solvers. Our experiments show that, despite mutex propagation being computationally expensive, it prunes the search space significantly so that the overall performance of MDD-SAT is improved.

This paper addresses a variant of multi-agent path finding (MAPF) in continuous space and time. We present a new solving approach based on satisfiability modulo theories (SMT) to obtain makespan optimal solutions. The standard MAPF is a task of navigating agents in an undirected graph from given starting vertices to given goal vertices so that agents do not collide with each other in vertices of the graph. In the continuous version (MAPF-R) agents move in an n-dimensional Euclidean space along straight lines that interconnect predefined positions. For simplicity, we work with circular omni-directional agents having constant velocities in the 2D plane. As agents can have different sizes and move smoothly along lines, a non-colliding movement along certain lines with small agents can result in a collision if the same movement is performed with larger agents. Our SMT-based approach for MAPF-R called SMT-CBS-R reformulates the Conflict-based Search (CBS) algorithm in terms of SMT concepts. We suggest lazy generation of decision variables and constraints. Each time a new conflict is discovered, the underlying encoding is extended with new variables and constraints to eliminate the conflict. We compared SMT-CBS-R and adaptations of CBS for the continuous variant of MAPF experimentally.

Multi-Agent Path Finding (MAPF) has been widely studied in the AI community. For example, Conflict-Based Search (CBS) is a state-of-the-art MAPF algorithm based on a two-level tree-search. However, previous MAPF algorithms assume that an agent occupies only a single location at any given time, e.g., a single cell in a grid. This limits their applicability in many real-world domains that have geometric agents in lieu of point agents. Geometric agents are referred to as “large” agents because they can occupy multiple points at the same time. In this paper, we formalize and study LAMAPF, i.e., MAPF for large agents. We first show how CBS can be adapted to solve LA-MAPF. We then present a generalized version of CBS, called Multi-Constraint CBS (MC-CBS), that adds multiple constraints (instead of one constraint) for an agent when it generates a high-level search node. We introduce three different approaches to choose such constraints as well as an approach to compute admissible heuristics for the high-level search. Experimental results show that all MC-CBS variants outperform CBS by up to three orders of magnitude in terms of runtime. The best variant also outperforms EPEA* (a state-of-the-art A*-based MAPF solver) in all cases and MDD-SAT (a state-of-the-art reduction-based MAPF solver) in some cases.

We describe an attempt to unify search-based and compilation-based approaches to multi-agent path finding (MAPF) through satisfiability modulo theories (SMT). The task in MAPF is to navigate agents in an undirected graph to given goal vertices so that they do not collide. We rephrase Conflict-Based Search (CBS), one of the state-of-the-art algorithms for optimal MAPF solving, in the terms of SMT. This idea combines SAT-based solving known from MDD-SAT, a SAT-based optimal MAPF solver, at the low level with conflict elimination of CBS at the high level. Where the standard CBS branches the search after a conflict occurs, we refine the propositional model with a disjunctive constraint instead. Our novel algorithm called SMT-CBS hence does not branch at the high-level but incrementally extends the propositional model that is consulted with the SAT solver at each iteration. We experimentally compare SMT-CBS with CBS and MDD-SAT.

Token swapping (TSWAP) represents a challenging problem underlying in many practical applications ranging from item relocation to quantum program compilation. In TSWAP, we are given an undirected graph with colored vertices. A colored token is placed in each vertex. A pair of tokens can be swapped between a pair of adjacent vertices. The goal is to perform a sequence of swaps so that token and vertex colors agree across the graph. The total number of swaps is usually required to be small. We study bounded sub-optimal algorithms for solving the TSWAP problem. We introduce a SAT-based algorithm based on lazy compilation of the problem to a Boolean formula and an alternative search-based algorithm using conflict based search. We analyze both algorithms experimentally on a number of benchmarks.

The At-Most-One (AMO) constraint is a special case of cardinality constraint that requires at most one variable from a set of Boolean variables to be set to $TRUE$ . AMO is important for modeling problems as Boolean satisfiability (SAT) from domains where decision variables represent spatial or temporal placements of some objects that cannot share the same spatial or temporal slot. The AMO constraint can be used for more efficient representation and problem solving in mutex networks consisting of pair-wise mutual exclusions forbidding pairs of Boolean variable to be simultaneously $TRUE$ . An on-line method for automated detection of cliques for efficient representation of incremental mutex networks where new mutexes arrive using AMOs is presented. A comparison of SAT-based problem solving in mutex networks represented by AMO constraints using various encodings is shown.

Multi-robot path planning (MRPP) is a task of planning collision free paths for a group of robots in a graph. Each robot starts in its individual starting vertex and its task is to reach a given goal vertex. Existing techniques for solving MRPP optimally under various objectives include search-based and compilation-based approaches. Often however finding an optimal solution is too difficult hence sub-optimal algorithms that trade-off the quality of solutions and the runtime have been devised. We suggest eSMT-CBS, a new bounded sub-optimal algorithm built on top of recent compilation-based method for optimal MRPP based on satisfiability modulo theories (SMT). We compare eSMT-CBS with ECBS, a major representative of bounded sub-optimal search-based algorithms. The experimental evaluation shows significant advantage of eSMT-CBS across variety of scenarios.

Multi-agent pathfinding (MAPF) represents a core problem in robotics. In its abstract form, the task is to navigate agents in an undirected graph to individual goal vertices so that conflicts between agents do not occur. Many algorithms for finding feasible or optimal solutions have been devised. We focus on the execution of MAPF solutions with a swarm of simple physical robots. Such execution is important for understanding how abstract plans can be transferred into reality and vital for educational demonstrations. We show how to use a swarm of reflex-based Ozobot Evo robots for MAPF execution. We emulate centralized control of the robots using their reflex-based behavior by putting them on a screen’s surface, where control curves are drawn in real-time during the execution. We identify critical challenges and ways to address them to execute plans successfully with the swarm. The MAPF execution was evaluated experimentally on various benchmarks.

Multi-agent path finding with continuous movements and time (denoted MAPF\(^\mathcal {R}\)) is addressed. The task is to navigate agents that move smoothly between predefined positions to their individual goals so that they do not collide. Recently a novel solving approach for obtaining makespan optimal solutions called SMT-CBS\(^\mathcal {R}\) based on satisfiability modulo theories (SMT) has been introduced. We extend the approach further towards the sum-of-costs objective which is a more challenging case in the yes/no SMT environment due to more complex calculation of the objective. The new algorithm combines collision resolution known from conflict-based search (CBS) with previous generation of incomplete propositional encodings on top of a novel scheme for selecting decision variables in a potentially uncountable search space. We experimentally compare SMT-CBS\(^\mathcal {R}\) and previous CCBS algorithm for MAPF\(^\mathcal {R}\).

We address engineering of smart behavior of agents in evacuation problems from the perspective of cooperative path finding (CPF) in this paper. We introduce an abstract version of evacuation problems we call multi-agent evacuation (MAE) that consists of an undirected graph representing the map of the environment and a set of agents moving in this graph. The task is to move agents from the endangered part of the graph into the safe part as quickly as possible. Although the abstract evacuation task can be solved using centralized algorithms based on network flows that are near-optimal with respect to various objectives, such algorithms would hardly be applicable in practice since real agents will not be able to follow the centrally created plan. Therefore we designed a decentralized evacuation planning algorithm called LC-MAE based on local rules derived from local cooperative path finding (CPF) algorithms. We compared LC-MAE with near-optimal centralized algorithm using agent-based simulations in multiple real-life scenarios. Our finding it that LC-MAE produces solutions that are only worse than the optimum by a small factor. Moreover our approach led to important observations about how many agents need to behave rationally to increase the speed of evacuation. A small fraction of rational agents can speed up the evacuation dramatically.

Multi-agent path finding with continuous movements and time (denoted MAPF\(^\mathcal {R}\)) is addressed. The task is to navigate agents that move smoothly between predefined positions to their individual goals so that they do not collide. Recently a novel solving approach for obtaining makespan optimal solutions called SMT-CBS\(^\mathcal {R}\) based on satisfiability modulo theories (SMT) has been introduced. We extend the approach further towards the sum-of-costs objective which is a more challenging case in the yes/no SMT environment due to more complex calculation of the objective. The new algorithm combines collision resolution known from conflict-based search (CBS) with previous generation of incomplete SAT encodings on top of a novel scheme for selecting decision variables in a potentially uncountable search space. We experimentally compare SMT-CBS\(^\mathcal {R}\) and previous CCBS (continuous conflict-based search) algorithm for MAPF\(^\mathcal {R}\).

We address variants of multi-robot path planning in graphs (MRPP). We assume robots placed in vertices of an undirected graph with at most one robot per vertex. Robots can move across edges while various problem specific constraints must be satisfied. We introduce a general problem formulation that encompasses known types of robot relocation problems such as multi-robot path planning (MRPP), token swapping (TSWAP), token rotation (TROT), and token permutation (TPERM). We generalize SMT-CBS, a recent solving approach for MRPP based on satisfiability modulo theories (SMT). SMT- CBS compiles MRPP lazily within the SMT framework, starting with the basic model that is refined with a collision resolution constraints whenever collisions between robots occur in the current solution. We show modifications the SMT-CBS algorithm for variants of MRPP and evaluate them experimentally.

Much of the literature on suboptimal, polynomial-time algorithms for multi-agent path finding focuses on undirected graphs, where motion is permitted in both directions along a graph edge. Despite this, traveling on directed graphs is relevant in navigation domains, such as path finding in games, and asymmetric communication networks.We consider multi-agent path finding on strongly biconnected directed graphs. We show that all instances with at least two unoccupied positions have a solution, except for a particular, degenerate subclass where the graph has a cyclic shape. We present diBOX, an algorithm for multi-agent path finding on strongly biconnected directed graphs. diBOX runs in polynomial time, computes suboptimal solutions and is complete for instances on strongly biconnected digraphs with at least two unoccupied positions. We theoretically analyze properties of the algorithm and properties of strongly biconnected directed graphs that are relevant to our approach. We perform a detailed empirical analysis of diBOX, showing a good scalability. To our knowledge, our work is the first study of multi-agent path finding focused on directed graphs.

This paper deals with solving cooperative path finding (CPF) problems in a makespan-optimal way. A feasible solution to the CPF problem lies in the moving of mobile agents where each agent has unique initial and goal positions. The abstraction adopted in CPF assumes that agents are discrete units that move over an undirected graph by traversing its edges. We focus specifically on makespan-optimal solutions to the CPF problem where the task is to generate solutions that are as short as possible in terms of the total number of time steps required for all agents to reach their goal positions. We demonstrate that reducing CPF to propositional satisfiability (SAT) represents a viable way to obtain makespan-optimal solutions. Several ways of encoding CPFs into propositional formulae are proposed and evaluated both theoretically and experimentally. Encodings based on the log and direct representations of decision variables are compared. The evaluation indicates that SAT-based solutions to CPF outperform the makespan-optimal versions of such search-based CPF solvers such as OD+ID, CBS, and ICTS in highly constrained scenarios (i.e., environments that are densely occupied by agents and where interactions among the agents are frequent). Moreover, the experiments clearly show that CPF encodings based on the direct representation of variables can be solved faster, although they are less space-efficient than log encodings.

We address conflict reasoning in generalizations of multi-agent path finding (MAPF). We assume items placed in vertices of an undirected graph with at most one item per vertex. Items can be relocated across edges while various constraints depending on the concrete type of MAPF must be satisfied. We recall a general problem formulation that encompasses known types of item relocation problems such as multi-agent path finding (MAPF) and token swapping (TSWAP). We show how to express new types of relocation problems in the general problem formulation. We thoroughly evaluate a novel solving method for item relocation that combines satisfiability modulo theory (SMT) with conflict-based search (CBS). CBS is interpreted in the SMT framework where we start with the basic model and refine the model with a collision resolution constraint whenever a collision between items occurs. The key difference between the standard CBS and the SMT-based modification of CBS (SMT-CBS) is that the standard CBS branches the search to resolve the collision while SMT-CBS iteratively adds a single disjunctive collision resolution constraint. Our experimental evaluation revealed that although SMT-CBS performs better than CBS in small densely occupied instances of variants of MAPF, it is outperformed on large sparsely occupied environments. The performed analysis shows that individual paths in large environments of relocation instances can be found faster using simple A*-based algorithm than by the SMT solver. On the other hand the SMT solver performs better when many conflicts between items need to be resolved.

In multi-agent path finding (MAPF) the task is to navigate agents from their starting positions to given individual goals. The problem takes place in an undirected graph whose vertices represent positions and edges define the topology. Agents can move to neighbor vertices across edges. In the standard MAPF, space occupation by agents is modeled by a capacity constraint that permits at most one agent per vertex. We suggest an extension of MAPF in this paper that permits more than one agent per vertex. Propositional satisfiability (SAT) models for these extensions of MAPF are studied. We focus on modeling capacity constraints in SAT-based formulations of MAPF and evaluation of performance of these models. We extend two existing SAT-based formulations with vertex capacity constraints: MDD-SAT and SMT-CBS where the former is an approach that builds the model in an eager way while the latter relies on lazy construction of the model.

This paper addresses optimal and near-optimal solving of the (N2–1)-puzzle using the A* search algorithm. We develop a novel heuristic based on artificial neural networks (ANNs) called ANN-distance that attempts to estimate the minimum number of moves necessary to reach the goal configuration of the puzzle. With a well trained ANN-distance heuristic, whose inputs are just the positions of the pebbles, we are able to achieve better accuracy of predictions than with conventional heuristics such as those derived from the Manhattan distance or pattern database heuristics. Though we cannot guarantee admissibility of ANN-distance, an experimental evaluation on random 15-puzzles shows that in most cases ANN-distance calculates the true minimum distance from the goal, and furthermore, A* search with the ANN-distance heuristic usually finds an optimal solution or a solution that is very close to the optimum. Moreover, the underlying neural network in ANN-distance consumes much less memory than a comparable pattern database.

This paper addresses evacuation problems from the perspective of cooperative path finding (CPF). The evacuation problem we call multi-agent evacuation (MAE) consists of an undirected graph and a set of agents. The task is to move agents from the endangered part of the graph into the safe part as quickly as possible. Although there exist centralized evacuation algorithms based on network flows that are optimal with respect to various objectives, such algorithms would hardly be applicable in practice since real agents will not be able to follow the centrally created plan. Therefore we designed a local evacuation planning algorithm called LC-MAE based on local CPF techniques. Agent-based simulations in multiple real-life scenarios show that LC-MAE produces solutions that are only worse than the optimum by a small factor. Moreover our approach led to important findings about how many agents need to behave rationally to increase the speed of evacuation.

This paper gives an overview of conflict reasoning in generalizations of multi-agent path finding (MAPF). MAPF and derived variants assume items placed in vertices of an undirected graph with at most one item per vertex. Items can be relocated across edges while various constraints depending on the concrete type of relocation problem must be satisfied. We recall a general problem formulation that encompasses known types of item relocation problems such as multi-agent path finding (MAPF), token swapping (TSWAP), token rotation (TROT), and token permutation (TPERM). We then focused on three existing optimal algorithms for MAPF: search-based CBS, and propositional satisfiability (SAT) - based MDD-SAT and SMT-CBS. These algorithms were modified to tackle various types of conflicts. The major contribution of this paper is a thorough experimental evaluation of CBS, MDD-SAT, and SMT-CBS on various types of relocation problems.

We study practical approaches to solving the token swapping (TSWAP) problem optimally in this paper. In TSWAP, we are given an undirected graph with colored vertices. A colored token is placed in each vertex. A pair of tokens can be swapped between adjacent vertices. The goal is to perform a sequence of swaps so that token and vertex colors agree across the graph. The minimum number of swaps is required in the optimization variant of the problem. We observed similarities between the TSWAP problem and multi-agent path finding (MAPF) where instead of tokens we have multiple agents that need to be moved from their current vertices to given unique target vertices. The difference between both problems consists in local conditions that state transitions (swaps/moves) must satisfy. We developed two algorithms for solving TSWAP optimally by adapting two different approaches to MAPF - conflict-based search (CBS) and SAT-based approach that uses multi-value decision diagrams (MDD-SAT). This constitutes the first attempt to design optimal solving algorithms for TSWAP. Experimental evaluation on various types of graphs shows that the reduction to SAT scales better than CBS in optimal TSWAP solving. It has been also demonstrated that TSWAP instances are easier to solve than corresponding similar MAPF instances.

The present paper deals with the problem of solving the ($$n^2 - 1$$n2-1)-puzzle and cooperative path-finding (CPF) problems sub-optimally by rule-based algorithms. To solve the puzzle, we need to rearrange $$n^2 - 1$$n2-1 pebbles in the $$n \times n$$n×n-sized square grid using one vacant position to achieve the goal configuration. An improvement to the existing polynomial-time algorithm is proposed and experimentally analyzed. The improved algorithm represents an attempt to move pebbles in a more efficient way compared to the original algorithm by grouping them into so-called snakes and moving them together as part of a snake formation. An experimental evaluation has shown that the snakeenhanced algorithm produces solutions which are 8---9 % shorter than the solutions generated by the original algorithm. Snake-like movement has also been integrated into the rule-based algorithms used in solving CPF problems sub-optimally, which is a closely related task. The task in CPF consists in moving a group of abstract robots on an undirected graph to specific vertices. The robots can move to unoccupied neighboring vertices; no more than one robot can be placed in each vertex. The ($$n^2 - 1$$n2-1)-puzzle is a special case of CPF where the underlying graph is a 4-connected grid and only one vertex is vacant. Two major rule-based algorithms for solving CPF problems were included in our study--BIBOX and PUSH-and-SWAP (PUSH-and-ROTATE). The use of snakes in the BIBOX algorithm led to consistent efficiency gains of around 30 % for the ($$n^2 - 1$$n2-1)-puzzle and up to 50 % in for CPF problems on biconnected graphs with various ear decompositions and multiple vacant vertices. For the PUSH-and-SWAP algorithm, the efficiency gain achieved from the use of snakes was around 5---8 %. However, the efficiency gain was unstable and hardly predictable for PUSH-and-SWAP.

We present and evaluate diBOX, an algorithm for multi-agent path finding on strongly biconnected directed graphs. diBOX runs in polynomial time, computes suboptimal solutions and is complete for instances on strongly biconnected digraphs with at least two unoccupied positions. A detailed empirical analysis shows a good scalability for diBOX.

In multi-agent path finding (MAPF) on graphs, the task is to find paths for distinguishable agents so that each agent reaches its unique goal vertex from the given start while collisions between agents are forbidden. A cumulative objective function is often minimized in MAPF. The main contribution of this paper consists in integrating independence detection technique (ID) into a compilation-based MAPF solver that translates MAPF instances into propositional satisfiability (SAT). The independence detection technique in search-based solvers tries to decompose a given MAPF instance into instances consisting of small groups of agents with no interaction across groups. After the decomposition phase, small instances are solved independently and the solution of the original instance is combined from individual solutions to small instances. The presented experimental evaluation indicates significant reduction of the size of instances translated to the target SAT formalism and positive impact on the overall performance of the solver.

The multi-agent pathfinding (MAPF) problem has attracted considerable attention because of its relation to practical applications. In this paper, we present a constraint-based declarative model for MAPF, together with its implementation in Picat, a logic-based programming language. We show experimentally that our Picat-based implementation is highly competitive and sometimes outperforms previous approaches. Importantly, the proposed Picat implementation is very versatile. We demonstrate this by showing how it can be easily adapted to optimize different MAPF objectives, such as minimizing makespan or minimizing the sum of costs, and for a range of MAPF variants. Moreover, a Picat-based model can be automatically compiled to several general-purpose solvers such as SAT solvers and Mixed Integer Programming solvers (MIP). This is particularly important for MAPF because some MAPF variants are solved more efficiently when compiled to SAT while other variants are solved more efficiently when compiled to MIP. We analyze these differences and the impact of different declarative models and encodings on empirical performance.

A parallel version of the problem of cooperative path-finding pCPF is introduced in this paper. The task in CPF is to determine a spatio-temporal plan for each member of a group of agents. Each agent is given its initial location in the environment and its task is to reach the given goal location. Agents must avoid obstacles and must not collide with one another. The environment where agents are moving is modeled as an undirected graph. Agents are placed in vertices and they move along edges. At most one agent is placed in each vertex and at least one vertex remains unoccupied. An agent can only move into a currently unoccupied vertex in the standard version of CPF. In the parallel version, an agent can also move into a vertex being currently vacated by another agent supposing the character of this movement is not cyclic. The optimal pCPF where the task is to find the smallest possible solution of the makespan is particularly studied. The main contribution of this paper is the proof of NP-completeness of the decision version of the optimal pCPF. A reduction of propositional satisfiability SAT to the problem is used in the proof.

The problem of mesh matching is addressed in this work. For a given n-sided planar region bounded by one loop of n polylines we are selecting optimal quadrilateral mesh from existing catalogue of meshes. The formulation of matching between planar shape and quadrilateral mesh from the catalogue is based on the problem of finding longest common subsequence (LCS). Theoretical foundation of mesh matching method is provided. Suggested method represents a viable technique for selecting best mesh for planar region and stepping stone for further parametrization of the region.

This paper proposes a framework for analyzing algorithms for inductive processing of bi-connected graphs. The BIBOX algorithm for solving cooperative path-finding problems over bi-connected graphs is submitted for the suggested analysis. The algorithm proceeds according to a decomposition of a given bi-connected graph into handles. After finishing a handle, the handle is ruled out of consideration and the processing task is reduced to a task of the same type on a smaller graph. The handle decomposition for which the BIBOX algorithm performs best is theoretically identified. The conducted experimental evaluation confirms that the suggested theoretical analysis well corresponds to the real situation.