Roman Barták

AAAI Conference 2026 Conference Paper

On Trustworthy, Explainable, and Verifiable High-Level Autonomy via Hierarchical Planning

• Roman Barták

Current mainstream AI, at least as presented in media and measured by the number of people involved and papers published, is mainly about big data, deep learning, and recently trendy large language models. All these are techniques that are data-driven, model-free, and number-crunching. Their immense success in some areas, such as computer vision and natural language processing, started the next hype in the era of AI, which brings a question whether neural approaches, after being dismissed at the beginning of the AI era, finally conquered the world of AI and proved applicable to every problem. A deeper look at these new techniques shows they have similar issues as the old-fashioned AI techniques in the past: brittleness, making strange mistakes, and being highly dependent on data used for training. Moreover, there are problems with the explainability of results and no guarantees provided, which is a crucial issue in some application areas. In this paper, we look at core principles of the neural ML techniques, that is, being data-driven rather than knowledge-based and being model-free rather than model-based, and we argue that symbolic knowledge models can still contribute to the design of trustworthy and explainable AI systems. Specifically, we focus on hierarchical reasoning, namely hierarchical planning, which is useful for highly complex problems but is not addressed by current neural models. We propose a research plan consisting of solving specific problems in hierarchical planning as an example of a knowledge-intensive approach to problem-solving. We show close connections between these problems that allow a smooth transition between solving techniques used to solve these problems. We also propose an ultimate goal of this endeavor, that is, autonomous construction of hierarchical planning models, that addresses the crucial problem of knowledge-based approaches -- how to obtain a formal model (extract knowledge from data).

IJCAI Conference 2025 Conference Paper

Using Planning for Automated Testing of Video Games

• Tomáš Balyo
• Roman Barták
• Lukáš Chrpa
• Michal Červenka
• Filip Dvořák
• Stephan Gocht
• Lukáš Lipčák
• Viktor Macek

In this demonstration, we present a system that automates regression testing for video games using automated planning techniques. Traditional test scripts are a common method for testing both video games and software in general. While effective, they require manual creation and frequent updates throughout development, making the process labor-intensive. Our system eliminates this burden by automatically generating and maintaining test scripts. The test engineer only needs to define the game’s rules using the Planning Domain Definition Language (PDDL) and specify initial states and goals for individual test cases. This significantly reduces human effort while ensuring test scripts remain up to date. Additionally, our system integrates with game engine editors—supporting both Unity and Unreal to execute and evaluate test cases directly within the game. It collects detailed logs, telemetry data, and video recordings, allowing users to review test results efficiently.

ECAI Conference 2025 Conference Paper

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

• Kristýna Pantucková
• 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.

KR Conference 2024 Conference Paper

Planning Domain Model Acquisition from State Traces without Action Parameters

• 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.

AIJ Journal 2023 Journal Article

Diagnosis of intermittent faults in Multi-Agent Systems: An SFL approach

• Avraham Natan
• Meir Kalech
• Roman Barták

Multi-Agent Systems (MAS) can be found in a wide variety of applications, including industrial systems, transportation, software systems and more. In such systems, agents may experience faults that affect the performance of the whole system. However, faulty agents might not consistently experience their fault, but rather in certain conditions. For example, a robot with a faulty rotating mechanism will appear healthy if it is tasked to only move in a straight line. Those faults are called Intermittent Faults. Such faults may cause the entire system to fail, but not always. Previous work proposed diagnosis algorithms for MAS, assuming faulty agents persistently behave abnormally. To the best of our knowledge, intermittent faults in MAS have not been concretely explored. In this paper we formally present a novel problem called Diagnosis of Intermittent Faults in Multi-Agent Systems (DIFMAS): a group of agents are observed across multiple runs. In each run, the success/failure of the agents and the system is observed, aiming to explain all the failed runs by diagnosing which agent(s) are faulty. The contributions of this paper are: (1) formalizing DIFMAS as a Model-Based Diagnosis problem, (2) solving it by presenting a Spectrum-Based Fault Localization (SFL) based method, called Multi-Run SFL-based Diagnosis Algorithm (MRSD). Experiments demonstrate that MRSD's outperforms competing SFL-based algorithms. Moreover, the algorithm's performance increases if planned interactions are considered.

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.

AAAI Conference 2023 Conference Paper

On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm

• Songtuan Lin
• Gregor Behnke
• Simona Ondrčková
• Roman Barták
• Pascal Bercher

In this paper, we consider the plan verification problem for totally ordered (TO) HTN planning. The problem is proved to be solvable in polynomial time by recognizing its connection to the membership decision problem for context-free grammars. Currently, most HTN plan verification approaches do not have special treatments for the TO configuration, and the only one features such an optimization still relies on an exhaustive search. Hence, we will develop a new TOHTN plan verification approach in this paper by extending the standard CYK parsing algorithm which acts as the best decision procedure in general.

HAXP Workshop 2023 Workshop Paper

Recognizing Hierarchical Plans via Earley Parsing

• Kristýna Pantůčková
• Roman Barták

ECAI Conference 2023 Conference Paper

Using Earley Parser for Recognizing Totally Ordered Hierarchical Plans

• Kristýna Pantucková
• Roman Barták

Earley Parser is a top-down parser proposed for context-free grammars and used, for example, in the grammar constraint. Parsing trees of context-free grammars are very close to task decomposition trees used in hierarchical planning, specifically when the actions are totally ordered. This paper suggests using the Earley Parser to recognize totally ordered hierarchical plans. Given a sequence of actions – a prefix of the plan – and a task decomposition model, the plan recognition problem asks which task decomposes to a plan containing the given plan prefix. We will show that the Earley parser significantly increases the speed of plan recognition compared to the existing bottom-up parsing-based plan recognizer. The Earley parser’s performance is also on a par with the planning-based plan recognizer despite not using any planning heuristics.

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.

AAMAS Conference 2022 Conference Paper

Reduction-based Solving of Multi-agent Pathfinding on Large Maps Using Graph Pruning

• Matej Husár
• Jiří Švancara
• Philipp Obermeier
• Roman Barták
• Torsten Schaub

Multi-agent pathfinding is the problem of finding collision-free paths for a set of agents. Solving this problem optimally is computationally hard, therefore many techniques based on reductions to other formalisms were developed. In comparison to search-based techniques, the reduction-based techniques fall behind on large maps even for a small number of agents. To combat this phenomenon, we propose several strategies for pruning vertices off large instances that will most likely not be used by agents. First, we introduce these strategies conceptually and prove which of them maintain completeness and optimality. Eventually, we conduct an exhaustive evaluation and show that graph pruning strategies make reduction-based solvers comparable to search-based techniques on large maps while maintaining their advantage on small dense maps.

SoCS Conference 2021 Conference Paper

Contingent Planning for Robust Multi-Agent Path Finding

• Michal Nekvinda
• Roman Barták
• Meir Kalech

A classical approach to Multi-agent Path Finding assumes an offline construction of collision-free paths that the agents blindly follow during execution. k-robust plans can be executed without collisions even if an agent is delayed for at most k steps. In the paper, we propose a novel concept of robustness that uses alternative paths to which the agents are diverted in case of delay. Such plans can be found with much higher chances than k-robust plans.

KR Conference 2021 Conference Paper

Correcting Hierarchical Plans by Action Deletion

• Roman Barták
• Simona Ondrčková
• Gregor Behnke
• Pascal Bercher

Hierarchical task network (HTN) planning is a model-based approach to planning. The HTN domain model consists of tasks and methods to decompose them into subtasks until obtaining primitive tasks (actions). There are recent methods for verifying if a given action sequence is a valid HTN plan. However, if the plan is invalid, all existing verification methods only say so without explaining why the plan is invalid. In the paper, we propose a method that corrects a given action sequence to form a valid HTN plan by deleting the minimal number of actions. This plan correction explains what is wrong with a given action sequence concerning the HTN domain model.

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.

AAAI Conference 2021 System Paper

OzoMorph: Demonstrating Colored Multi-Agent Path Finding on Real Robots

• Roman Barták
• Jakub Mestek

Multi-agent Path Finding (MAPF) deals with finding collision-free paths for a set of agents on a graph, where each agent has its origin and destination. Colored MAPF is a generalization of MAPF, where groups of agents are moving, and the set of destination nodes is specified per group rather than per agent. OzoMorph is software providing an intuitive user interface for specifying Colored MAPF problems, solving them by translation to SAT, and finally visualizing the solution either in a computer simulation or by converting the plans to executable instructions for Ozobot Evo robots.

AAAI Conference 2020 System Paper

MAPF Scenario: Software for Evaluating MAPF Plans on Real Robots

• Roman Barták
• Jiří Švancara
• Ivan Krasičenko

Multi-Agent Path Finding (MAPF) deals with finding collision free paths for a set of agents (robots) moving on a graph. The interest in MAPF in the research community started to increase recently partly due to practical applications in areas such as warehousing and computer games. However, the academic community focuses mostly on solving the abstract version of the problem (moving of agents on the graph) with only a few results on real robots. The presented software MAPF Scenario provides a tool for specifying MAPF problems on grid maps, solving the problems using various abstractions (for example, assuming rotation actions or not), simulating execution of plans, and translating the abstract plans to control programs for small robots Ozobots. The tool is intended as a research platform for evaluating abstract MAPF plans on real robots and as an educational and demonstration tool bridging the areas of artificial intelligence and robotics.

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.

JAIR Journal 2020 Journal Article

Robust Multi-Agent Path Finding and Executing

• Dor Atzmon
• Roni Stern
• Ariel Felner
• Glenn Wagner
• Roman Barták
• Neng-Fa Zhou

Multi-agent path-finding (MAPF) is the problem of finding a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. In this work, we propose a holistic solution for MAPF that is robust to such unexpected delays. First, we introduce the notion of a k-robust MAPF plan, which is a plan that can be executed even if a limited number (k) of delays occur. We propose sufficient and required conditions for finding a k-robust plan, and show how to convert several MAPF solvers to find such plans. Then, we propose several robust execution policies. An execution policy is a policy for agents executing a MAPF plan. An execution policy is robust if following it guarantees that the agents reach their goals even if they encounter unexpected delays. Several classes of such robust execution policies are proposed and evaluated experimentally. Finally, we present robust execution policies for cases where communication between the agents may also be delayed. We performed an extensive experimental evaluation in which we compared different algorithms for finding robust MAPF plans, compared different ro- bust execution policies, and studied the interplay between having a robust plan and the performance when using a robust execution policy.

IJCAI Conference 2019 Conference Paper

Multi-Agent Path Finding on Ozobots

• Roman Barták
• Ivan Krasičenko
• Jiří Švancara

Multi-agent path finding (MAPF) is the problem to find collision-free paths for a set of agents (mobile robots) moving on a graph. There exists several abstract models describing the problem with various types of constraints. The demo presents software to evaluate the abstract models when the plans are executed on Ozobots, small mobile robots developed for teaching programming. The software allows users to design the grid-like maps, to specify initial and goal locations of robots, to generate plans using various abstract models implemented in the Picat programming language, to simulate and to visualise execution of these plans, and to translate the plans to command sequences for Ozobots.

AAMAS Conference 2019 Conference Paper

Multi-Agent Path Finding on Real Robots

• Roman Barták
• Ivan Krasičenko
• Jičí Švancara

Multi-agent path finding (MAPF) deals with the problem of finding a collision-free path for a set of agents in a graph. It is an abstract version of the problem to coordinate movement for a set of mobile robots. This demo presents software guiding through the MAPF task, starting from the problem formulation and finishing with execution of plans on real robots. Users can design grid-like maps, specify initial and goal locations of robots, generate plans using various abstract models implemented in the Picat programming language, simulate and visualize execution of these plans, and translate the plans to command sequences for Ozobots, small robots developed for teaching programming.

SoCS Conference 2019 Conference Paper

Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

• Roni Stern
• Nathan R. Sturtevant
• Ariel Felner
• Sven Koenig
• Hang Ma 0001
• Thayne T. Walker
• Jiaoyang Li 0001
• Dor Atzmon

The multi-agent pathfinding problem (MAPF) is the fundamental problem of planning paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other. Applications of MAPF include automated warehouses, autonomous vehicles, and robotics. Research on MAPF has been flourishing in the past couple of years. Different MAPF research papers assume different sets of assumptions, e. g. , whether agents can traverse the same road at the same time, and have different objective functions, e. g. , minimize makespan or sum of agents

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.

AAAI Conference 2019 Conference Paper

Online Multi-Agent Pathfinding

• Jiří Švancara
• Marek Vlk
• Roni Stern
• Dor Atzmon
• Roman Barták

Multi-agent pathfinding (MAPF) is the problem of moving a group of agents to a set of target destinations while avoiding collisions. In this work, we study the online version of MAPF where new agents appear over time. Several variants of online MAPF are defined and analyzed theoretically, showing that it is not possible to create an optimal online MAPF solver. Nevertheless, we propose effective online MAPF algorithms that balance solution quality, runtime, and the number of plan changes an agent makes during execution.

SoCS Conference 2018 Conference Paper

Robust Multi-Agent Path Finding

• Dor Atzmon
• Roni Stern
• Ariel Felner
• Glenn Wagner
• Roman Barták
• Neng-Fa Zhou

In the multi-agent path-finding (MAPF) problem, the task is to find a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. We explore the notion of k-robust MAPF, where the task is to find a plan that can be followed even if a limited number of such delays occur. k-robust MAPF is especially suitable for agents with a control mechanism that guarantees that each agent is within a limited number of steps away from its pre-defined plan. We propose sufficient and required conditions for finding a k-robust plan, and show how to convert several MAPF solvers to find such plans. Then, we show the benefit of using a k-robust plan during execution, and for finding plans that are likely to succeed.

ICAPS Conference 2018 Conference Paper

Validation of Hierarchical Plans via Parsing of Attribute Grammars

• Roman Barták
• Adrien Maillard
• Rafael C. Cardoso 0001

An important problem of automated planning is validating if a plan complies with the domain model. Such validation is straightforward for classical sequential planning but until recently there was no plan validation approach for Hierarchical Task Networks (HTN). In this paper we propose a novel technique for validating HTN plans by parsing of attribute grammars with the timeline constraint.

SoCS Conference 2017 Conference Paper

k-Robust Multi-Agent Path Finding

• Dor Atzmon
• Ariel Felner
• Roni Stern
• Glenn Wagner
• Roman Barták
• Neng-Fa Zhou

In the multi-agent path-finding (MAPF) problem a plan is needed to move a set of agents from their initial location to their goals without collisions. In this paper we introduce and study the k-robust MAPF problem, where we seek a plan that is robust to k unexpected delays per agent.

KER Journal 2016 Journal Article

Introduction to the special issue on constraint satisfaction for planning and scheduling

• Miguel A. Salido
• Roman Barták

Abstract The areas of Artificial Intelligence planning and scheduling have seen important advances thanks to the application of constraint satisfaction models and techniques. Especially, solutions to many real-world problems need to integrate plan synthesis capabilities with resource allocation, which can be efficiently managed by using constraint satisfaction techniques. Constraint satisfaction plays an important role in solving such real life problems, and integrated techniques that manage planning and scheduling with constraint satisfaction are particularly useful.

SoCS Conference 2015 Conference Paper

No One SATPlan Encoding To Rule Them All

• Tomás Balyo
• Roman Barták

Solving planning problems via translation to propositional satisfiability (SAT) is one of the most successful approaches to automated planning. An important aspect of this approach is the encoding, i. e. , the construction of a propositional formula from a given planning problem instance. Numerous encoding schemes have been proposed in the recent years each aiming to outperform the previous encodings on the majority of the benchmark problems. In this paper we take a different approach. Instead of trying to develop a new encoding that is better for all kinds of benchmarks we take recently developed specialized encoding schemes and design a method to automatically select the proper encoding for a given planning problem instance. In the paper we also examine ranking heuristics for the Relaxed Relaxed Exists-Step encoding, which plays an important role in our algorithm. Experiments show that our new approach significantly outperforms the state-of-the-art encoding schemes when compared on the benchmarks of the 2011 International Planning Competition.

KER Journal 2013 Journal Article

Preface to special issue on Knowledge Engineering for Planning and Scheduling

• Roman Barták
• Simone Fratini
• Thomas Leo McCluskey

ECAI Conference 2012 Conference Paper

FlowOpt: Bridging the Gap Between Optimization Technology and Manufacturing Planners

• Roman Barták
• Milan Jaska
• Ladislav Novak
• Vladimír Rovenský
• Tomás Skalický
• Martin Cully
• Con Sheahan
• Thanh-Tung Dang

FlowOpt is an integrated collection of tools for workflow optimization in production environments. It was developed as a demonstration of advancements in the areas of modeling and optimization with the focus on simplifying the usage of the technology for end customers. The system consists of several interconnected modules. First, the user visually models a workflow describing the production of some item. Then the user specifies which items and how many of them should be produced (order management) and the system automatically generates a production schedule. This schedule is then visualized in the form of a Gantt chart where the user can arbitrarily modify the schedule. Finally, the system can analyze the schedule and suggest some improvements such as buying a new machine. Constraint satisfaction technology is the solving engine behind these modules.

SoCS Conference 2012 Conference Paper

On Improving Plan Quality via Local Enhancements

• Tomás Balyo
• Roman Barták
• Pavel Surynek

There exist planning algorithms that can quickly find sub-optimal plans even for large problems and planning algorithms finding optimal plans but only for smaller problems. We attempt to integrate both approaches. We present an anytime technique for improving plan quality (decreasing the plan makespan) via substituting parts of the plan by better sub-plans. The technique guarantees optimality though it is primarily intended to quickly improve plan quality. We experimentally compare various approaches to local improvements.

KER Journal 2010 Journal Article

New trends in constraint satisfaction, planning, and scheduling: a survey

• Roman Barták
• Miguel A. Salido
• Francesca Rossi

Abstract During recent years, the development of new techniques for constraint satisfaction, planning, and scheduling has received increased attention, and substantial effort has been invested in trying to exploit such techniques to find solutions to real-life problems. In this paper, we present a survey on constraint satisfaction, planning, and scheduling from the Artificial Intelligence point of view. In particular, we present the main definitions and techniques, and discuss possible ways of integrating such techniques. We also analyze the role of constraint satisfaction in planning and scheduling, and hint at some open research issues related to planning, scheduling, and constraint satisfaction.

KER Journal 2010 Journal Article

Preface to special issue on planning and scheduling

• Roman Barták
• Amedeo Cesta
• Lee McCluskey
• Miguel A. Salido

Abstract Planning, scheduling and constraint satisfaction are important areas in artificial intelligence (AI) with broad practical applicability. Many real-world problems can be formulated as AI planning and scheduling (P&S) problems, where resources must be allocated to optimize overall performance objectives. Frequently, solving these problems requires an adequate mixture of planning, scheduling and resource allocation to competing goal activities over time in the presence of complex state-dependent constraints. Constraint satisfaction plays an important role in solving such real-life problems, and integrated techniques that manage P&S with constraint satisfaction are particularly useful. Knowledge engineering supports the solution of such problems by providing adequate modelling techniques and knowledge extraction techniques for improving the performance of planners and schedulers. Briefly speaking, knowledge engineering tools serve as a bridge between the real world and P&S systems.

EAAI Journal 2008 Journal Article

Introduction: Special issue on constraint satisfaction techniques for planning and scheduling problems

• Miguel A. Salido
• Antonio Garrido
• Roman Barták

KER Journal 2007 Journal Article

Introduction to the Special Issue on Knowledge Engineering Tools and Techniques for Automated Planning and Scheduling Systems

• Roman Barták
• Lee McCluskey

ICAPS Conference 2006 Conference Paper

Incremental Maintenance of Double Precedence Graphs: A Constraint-Based Approach

• Roman Barták
• Ondrej Cepek

Reasoning on precedence relations is crucial for many planning and scheduling systems. In this paper we propose a double precedence graph where direct precedence relations are kept additionally to traditional precedence relations (A can directly precede B if no activity must be allocated between A and B). Such precedence relations are motivated by solving problems like modelling sequence-dependent setup times or describing state transitions. We describe a constraint-based model for double precedence graphs and present incremental propagation rules for maintaining the transitive closure of the graph.

AIJ Journal 2005 Journal Article

Book review

• Roman Barták

ECAI Conference 2002 Conference Paper

A Theoretical Framework for Constraint Hierarchy Solvers

• Roman Barták

ICAPS Conference 2002 Conference Paper

Filtering Algorithms for Batch Processing with Sequence Dependent Setup Times

• Petr Vilím
• Roman Barták

Domain filtering is a powerful technique for reduction of the search space during solving combinatorial problems like scheduling. In this paper we present several filtering algorithms designed specifically for scheduling in batch processing environments with sequence dependent setup times. We extend two known algorithms, namely edge finding and not-first/not-last technique, and we present a new filtering algorithm called not-before/not-after. Each of these algorithms removes some inconsistencies that are not detected by the other two algorithms. Thus, all the algorithms are assumed to run together to achieve better pruning.