Author name cluster

Jirí Svancara

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

SoCS Conference 2023 Conference Paper

Multi-Agent Pathfinding with Predefined Paths: To Wait, or Not to Wait, That Is the Question [Extended Abstract]

Jirí Svancara
Etienne Tignon
Roman Barták
Torsten Schaub
Philipp Wanko
Roland Kaminski

Multi-agent pathfinding is the task of navigating a set of agents in a shared environment without collisions. Finding an optimal plan is a computationally hard problem, therefore, one may want to sacrifice optimality for faster computation time. In this paper, we present our preliminary work on finding a valid solution using only a predefined path for each agent with the possibility of adding wait actions. This restriction makes some instances unsolvable, however, we show instances where this approach is guaranteed to find a solution.

Details

SoCS Conference 2022 Conference Paper

Multi-agent Pathfinding on Large Maps Using Graph Pruning: This Way or That Way? (Extended Abstract)

Jirí Svancara
Philipp Obermeier
Matej Husár
Roman Barták
Torsten Schaub

This paper extends a study on improving the performance of reduction-based solvers for the problem of multi-agent pathfinding. The task is to navigate a set of agents in a graph without collisions. Solvers that reduce this problem to other formalisms often have issues scaling to larger instances in terms of the graph size. A previous study suggests that pruning the graph of most vertices based on a randomly chosen shortest path for each agent. In this paper, we study the effect of different choices of these paths.

Details

SoCS Conference 2021 Conference Paper

From Classical to Colored Multi-Agent Path Finding

Roman Barták
Marika Ivanová
Jirí Svancara

Multi-Agent Path Finding (MAPF) deals with the problem of finding collision-free paths for a set of agents moving in a shared environment, while each agent has specified its own destination. Colored MAPF generalizes MAPF by defining groups of agents that share a set of destination locations. In the paper, we evaluate several approaches to optimally solve colored MAPF problem, namely, a method based on network flows, an extended version of conflict-based search, and two models using Boolean satisfiability. We also investigate methods for obtaining lower bounds on optimal solutions based on constraint and continuous relaxation techniques.

Details

SoCS Conference 2020 Conference Paper

On Modelling Multi-Agent Path Finding as a Classical Planning Problem

Jindrich Vodrázka
Roman Barták
Jirí Svancara

Multi-Agent Path Finding (MAPF) deals with the problem of finding collision-free paths for a set of agents, where each agent wants to move from its start location to its goal location on a shared graph. The paper addresses the question of how to model MAPF as a classical planning problem, specifically, how to encode various collision constraints. Several models in the PDDL modeling language are proposed and empirically compared.

Details

SoCS Conference 2019 Conference Paper

On SAT-Based Approaches for Multi-Agent Path Finding with the Sum-of-Costs Objective

Roman Barták
Jirí Svancara

Multi-agent path finding (MAPF) deals with the problem of finding collision-free paths for a set of agents. Each agent moves from its start location to its destination location in a shared environment represented by a graph. Reduction-based solving approaches for MAPF, for example reduction to SAT, exploit a time-expended layered graph, where each layer corresponds to specific time. Hence, these approaches are natural for minimizing makespan (the shortest time till all agents reach their destinations). Modeling the other frequently used objective, namely Sum of Costs (SOC; sum of paths lengths of all agents) is more difficult as the solution with the smallest SOC may not be reached in the time-expended graph with the smallest makespan. In this paper we suggest two novel approaches to estimate the makespan, that guarantees existence of a SOC-optimal solution. The approaches are empirically compared with an existing reduction-based method as well as with the state-of-the-art search-based optimal MAPF solver.

Details