RBRoman Barták

Roman Barták

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Roman Barták has a total of 178 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    42+ Flavors of Multi-Agent Path Finding

    by David Zahrádka, Miroslav Kulich, Jiří Švancara, Roman Barták

    Multi-Agent Path Finding (MAPF) is a well-studied problem. In recent years, many derivations of MAPF – MAPF flavors – have been formulated and solved. Although some flavors only lift some assumptions present in MAPF, others result from combining two or more flavors. So far, no published work has focused specifically on these newly derived problems, which resulted in incomplete coverage of this area of MAPF, even if it enjoys significant research focus. We present a survey on MAPF flavors, in which we collected 48 existing MAPF-derived problems, categorized them, identified their key defining features, and mapped the relationships between them. The survey is designed to serve as a crossroads for both new and experienced researchers looking to obtain or update their knowledge about MAPF-adjacent problems and readers with such a problem looking for a solution or a reference method. The collected problems are therefore presented in a way that allows an interested reader to find and identify both new and related problems, learn about the state-of-the-art solution methods, and find literature that explains them in greater detail.

  • A Holistic Architecture for Monitoring and Optimization of Robust Multi-agent Path Finding Plan Execution

    by David Zahrádka, Denisa Mužíková, David Woller, Miroslav Kulich, Jiří Švancara, Roman Barták

  • Open Access

    The Effect of Decomposition Rule Modeling on the Efficiency of Hierarchical Planners

    by Roman Bartak, Simona Ondrčková, Kristýna Pantůčková

    Hierarchical planning is a widely used approach in automated planning that breaks down complex tasks into manageable subtasks, facilitating more efficient problem-solving. The task decomposition is modelled via decomposition rules that resemble rewriting rules of context-free grammars. Normal forms for rewriting rules, namely Chomsky Normal Form and Greibach Normal Form, have been proposed in the context of formal grammars and also applied to hierarchical planning models, specifically for hierarchical plan verification. This paper examines whether the format of decomposition rules also influences the efficiency of hierarchical planners.

  • Open Access

    Ghost Agents in SAT-based Models for Multi-Agent Pathfinding

    by Jiří Švancara, Roman Barták

    Multi-agent pathfinding (MAPF) is the task of navigating a set of mobile agents in a shared environment while avoiding collisions when multiple agents occupy the same space simultaneously. One popular approach to solving MAPF is to transform the problem into a different formalism, such as Boolean satisfiability (SAT), and solve the problem using an off-the-shelf SAT solver. The current state-of-the-art SAT-based MAPF solvers model the position of each agent at each timestep as a Boolean variable and enforce valid movement and coordination via constraints among those variables encoded as a logical formula. It might be expected that the formula encodes a single valid, collision-free path for each agent, meaning that at any given time, each agent occupies exactly one location. In this paper, we explore the possibility of an agent being present at multiple locations simultaneously. While such relaxed encoding exists in the literature, the presence of duplicate agents is not discussed. In this paper, we coin the term ghost agents and show that their presence does not hinder the validity of the solution. As the relaxed encoding reduces the size of the formula, we compare it empirically. Furthermore, we compare empirically all approaches used in reduction-based MAPF solving and their combinations: single and ghost agents, with eager and lazy encodings of conflicts under both the makespan and the sum-of-costs objectives. The experiments show that no combination is a clear winner in all types of instances.

  • Open Access

    What to Do if a Plan Does Not Comply with an HTN Model?

    by Kristýna Pantůčková, Roman Barták

    Plan verification deals with the problem of checking whether a given sequence of actions is a valid plan according to a planning domain model. If the action sequence is not a valid plan, the next question is where the problem is. This question can be addressed by plan correction – modifying the plan to get a valid plan. The paper presents the first system to correct totally ordered hierarchical plans by action deletion and action insertion. Supporting action insertion, which is the major novelty here, significantly extends the applicability of plan correction to areas such as plan recognition and even planning itself. The new system is also faster than the existing plan correction system when only action deletion is allowed.

  • Open Access

    Knowledge Engineering for Planning and Scheduling in the LLM Era

    by Mauro Vallati, Roman Barták, Lukáš Chrpa, Thomas L. McCluskey, Ronald P. A. Petrick

    Automated planning requires explicit domain knowledge, typically represented in PDDL, to generate effective solutions. The process of formulating, maintaining, and validating this knowledge is the cornerstone of Knowledge Engineering for Planning and Scheduling (KEPS). Although Large Language Models (LLMs) have shown promise for automated planning tasks, and are gaining popularity in the field, their impact on KEPS remains unexplored. In this paper we investigate the potential of LLMs to streamline and enhance the KEPS field, by taking a close look at the processes used to develop explicit symbolic knowledge models in safety-related applications. The paper's findings are that while LLMs can assist in knowledge acquisition and formulation, human domain expertise and external symbolic validators remain indispensable for ensuring correctness, operationality and completeness of planning applications.


  • Open Access

    On Path Selection for Reduction-Based Solving of Multi-Agent Pathfinding Using Graph Pruning

    by Matej Husár, Jiří Švancara, Roman Barták

    Multi-agent pathfinding is the task of navigating a set of mobile agents in a shared environment such that they avoid collisions. Finding an optimal solution in terms of the length of the plan is known to be a computationally hard problem (NP-Hard). In general, there are two schools of optimal algorithms: search-based and reduction-based. While search-based algorithms excel in solving large maps where few conflicts can be expected, reduction-based algorithms excel in smaller instances even when agents interact often. However, the reduction-based approaches lag behind in large instances, even with few agents. To mitigate this, a subgraph pruning method was introduced to prune unnecessary vertices to decrease the size of the instance. The pruning is based on the shortest paths for each agent. In the original study, the authors randomly selected the shortest routes. In this study, we replicate the overall approach while selecting the initial shortest path with more care. We provide several approaches for selecting one of the possible shortest paths and experimentally compare them. We note that when the makespan optimal plan is needed, not all agents are required to use the shortest path, as only the longest path dictates the makespan. Using this observation, we also introduce an approach that selects longer paths for some agents if it helps to reduce the total number of interactions between agents. We provide an experimental comparison of all proposed approaches and show that the latter performs significantly better, in most cases outperforming any approach that strictly selects only the shortest path.


  • Open Access

    Hierarchical Plan Repair via Plan Recognition and Plan Correction

    by Kristýna Pantůčková, Roman Barták

    Hierarchical planning extends classical planning by introducing a hierarchy of tasks describing how tasks decompose into subtasks until primitive tasks -- actions -- forming a plan are obtained. Plan repair deals with plans that failed to execute due to a sudden state change. In particular, plan repair modifies the not-yet executed suffix of the plan to achieve the original goal. Hierarchical plan repair aims to modify a partially executed plan while respecting the task hierarchy. This paper describes how hierarchical plan repair can be realized by solving closely related hierarchical plan recognition and correction problems.

  • Open Access

    On Removing Left Recursion from Totally-ordered HTN Domain Models

    by Simona Ondrčková, Roman Barták, Vladislav Kuboň

    Hierarchical planning is a knowledge-based approach to automated planning, where high-level (compound)tasks are decomposed into simpler tasks until primitive tasks – actions – forming the plan are obtained. Hierarchical Task Networks (HTN) is a modeling formalism for hierarchical planning, where task decompositions are described using decomposition methods with specific constraints. These decomposition methods are very close to rewriting (production) rules of context-free grammars, specifically when the domain is totally ordered. Recursive rules, when a task decomposes to it self, are generally allowed. Generating plans from left to right brings advantage of the first actions in the plan to be ready for execution even if the plan is not yet fully generated. However, left recursion goes against this idea as it tends to generate the plan from right (end) till left (beginning). The paper shows how to remove left recursion from HTN decomposition methods using the ideas from the Greibach Normal Form.

  • Open Access

    Planning Domain Model Acquisition from State Traces without Action Parameters

    by Tomáš Balyo, Martin Suda, Lukáš Chrpa, Dominik Šafránek, Stephan Gocht, Filip Dvořák, Roman Barták, G. Michael Youngblood

    Existing planning action domain model acquisition approaches consider different types of state traces from which they learn. The differences in state traces refer to the level of observability of state changes (from full to none) and whether the observations have some noise (the state changes might be inaccurately logged). However, to the best of our knowledge, all the existing approaches consider state traces in which each state change corresponds to an action specified by its name and all its parameters (all objects that are relevant to the action). Furthermore, the names and types of all the parameters of the actions to be learned are given. These assumptions are too strong. In this paper, we propose a method that learns action schema from state traces with fully observable state changes but without the parameters of actions responsible for the state changes (only action names are part of the state traces). Although we can easily deduce the number (and names) of the actions that will be in the learned domain model, we still need to deduce the number and types of the parameters of each action alongside its precondition and effects. We show that this task is at least as hard as graph isomorphism. However, our experimental evaluation on a large collection of IPC benchmarks shows that our approach is still practical as the number of required parameters is usually small. Compared to the state-of-the-art learning tools SAM and Extended SAM our new algorithm can provide better results in terms of learning action models more similar to reference models, even though it uses less information and has fewer restrictions on the input traces.