Author name cluster

Lukás Chrpa

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.

23 papers

1 author row

ICAPS Conference 2024 Conference Paper

On Verifying Linear Execution Strategies in Planning Against Nature

Lukás Chrpa
Erez Karpas

While planning and acting in environments in which nature can trigger non-deterministic events, the agent has to consider that the state of the environment might change without its consent. Practically, it means that the agent has to make sure that it eventually achieves its goal (if possible) despite the acts of nature. In this paper, we first formalize the semantics of such problems in Alternating-time Temporal Logic, which allows us to prove some theoretical properties of different types of solutions. Then, we focus on linear execution strategies, which resemble classical plans in that they follow a fixed sequence of actions. We show that any problem that can be solved by a linear execution strategy can be solved by a particular form of linear execution strategy which assigns wait-for preconditions to each action in the plan that specifies when to execute that action. Then, we propose a sound algorithm that verifies a sequence of actions and assigns wait-for preconditions to them by leveraging abstraction.

ICAPS Conference 2024 Conference Paper

Weak and Strong Reversibility of Non-deterministic Actions: Universality and Uniformity

Jakub Med
Lukás Chrpa
Michael Morak
Wolfgang Faber 0001

Classical planning looks for a sequence of actions that transform the initial state of the environment into a goal state. Studying whether the effects of an action can be undone by a sequence of other actions, that is, action reversibility, is beneficial, for example, in determining whether an action is safe to apply. This paper deals with action reversibility of non-deterministic actions, i. e. , actions whose application might result in different outcomes. Inspired by the established notions of weak and strong plans in non-deterministic (or FOND) planning, we define the notions of weak and strong reversibility for non-deterministic actions. We then focus on the universality and uniformity of action reversibility, that is, whether we can always undo all possible effects of the action by the same means (i. e. , policy), or whether some of the effects can never be undone. We show how these classes of problems can be solved via classical or FOND planning and evaluate our approaches on FOND benchmark domains.

JELIA Conference 2023 Conference Paper

Comparing Planning Domain Models Using Answer Set Programming

Lukás Chrpa
Carmine Dodaro
Marco Maratea
Marco Mochi
Mauro Vallati

Abstract Automated planning is a prominent area of Artificial Intelligence, and an important component for intelligent autonomous agents. A critical aspect of domain-independent planning is the domain model, that encodes a formal representation of domain knowledge needed to reason upon a given problem. Despite the crucial role of domain models in automated planning, there is lack of tools supporting knowledge engineering process by comparing different versions of the models, in particular, determining and highlighting differences the models have. In this paper, we build on the notion of strong equivalence of domain models and formalise a novel concept of similarity of domain models. To measure the similarity of two models, we introduce a directed graph representation of lifted domain models that allows to formulate the domain model similarity problem as a variant of the graph edit distance problem. We propose an Answer Set Programming approach to optimally solve the domain model similarity problem, that identifies the minimum number of modifications the models need to become strongly equivalent, and we demonstrate the capabilities of the approach on a range of benchmark models.

JELIA Conference 2023 Conference Paper

Enhancing Temporal Planning by Sequential Macro-Actions

Marco De Bortoli
Lukás Chrpa
Martin Gebser
Gerald Steinbauer-Wagner

Abstract Temporal planning is an extension of classical planning involving concurrent execution of actions and alignment with temporal constraints. Unfortunately, the performance of temporal planning engines tends to sharply deteriorate when the number of agents and objects in a domain gets large. A possible remedy is to use macro-actions that are well-studied in the context of classical planning. In temporal planning settings, however, introducing macro-actions is significantly more challenging when the concurrent execution of actions and shared use of resources, provided the compliance to temporal constraints, should not be suppressed entirely. Our work contributes a general concept of sequential temporal macro-actions that guarantees the applicability of obtained plans, i. e. , the sequence of original actions encapsulated by a macro-action is always executable. We apply our approach to several temporal planners and domains, stemming from the International Planning Competition and RoboCup Logistics League. Our experiments yield improvements in terms of obtained satisficing plans as well as plan quality for the majority of tested planners and domains.

SoCS Conference 2023 Conference Paper

Towards an Effective Framework Combining Planning and Scheduling [Extended Abstract]

Andrii Nyporko
Lukás Chrpa

In a nutshell, Automated Planning deals with finding sequences of actions that achieve a required goal while scheduling deals with allocating activities on (limited) resources meeting specified constraints. Activities, however, might resemble actions in planning as we might capture what they can produce and under what conditions. That said, the "planning

SoCS Conference 2022 Conference Paper

Deep RRT

Xuzhe Dang
Lukás Chrpa
Stefan Edelkamp

Sampling-based motion planning algorithms such as Rapidly exploring Random Trees (RRTs) have been used in robotic applications for a long time. In this paper, we propose a method that combines deep learning with RRT* method. We use a neural network to learn a sample strategy for RRT*. We evaluate Deep RRT* in a collection of 2D scenarios. The results demonstrate that our algorithm could find collision-free paths efficiently and fast, and can be generalized to unseen environments.

SoCS Conference 2022 Conference Paper

Effective Planning in Resource-Competition Problems by Task Decomposition

Lukás Chrpa
Pavel Rytír
Andrii Nyporko
Rostislav Horcík
Stefan Edelkamp

Effective planning while competing for limited resources is crucial in many real-world applications such as on-demand transport companies competing for passengers. Planning techniques therefore have to take into account possible actions of an adversarial agent. Such a challenge that can be tackled by leveraging game-theoretical methods such as Double Oracle. This paper aims at the scalability issues arising from combining planning techniques with Double Oracle. In particular, we propose an abstraction-based heuristic for deciding how resources will be collected (e. g. which car goes for which passenger and in which order) and we propose a method for decomposing planning tasks into smaller ones (e. g. generate plans for each car separately). Our empirical evaluation shows that our proposed approach considerably improves scalability compared to the state-of-the-art techniques.

ICAPS Conference 2022 Conference Paper

On Speeding Up Methods for Identifying Redundant Actions in Plans

Jakub Med
Lukás Chrpa

Satisficing planning aims at generating plans that are not necessarily optimal. Often, minimising plan generation time negatively affects quality of generated plans. Acquiring plans quickly might be of critical importance in decision-making systems that operate nearly in realtime. However, (very) suboptimal plans might be expensive to execute and more prone to failures. Optimising plans after they are generated, in a spare time, can improve their quality. This paper focuses on speeding up the (Greedy) Action Elimination methods, which are used for identifying and removing redundant actions from plans in polynomial time. We present two enhancements of these methods: Plan Action Landmarks, actions that are not redundant in a given plan, and Action Cycles which are subsequences of actions which if removed do not affect the state trajectory after the last action of the cycle. We evaluate the introduced methods on benchmark problems from the Agile tracks of the International Planning Competition and on plans generated by several state-of-the-art planners, successful in the recent editions of the competition.

ICAPS Conference 2022 Conference Paper

Optimal Mixed Strategies for Cost-Adversarial Planning Games

Rostislav Horcík
Álvaro Torralba
Pavel Rytír
Lukás Chrpa
Stefan Edelkamp

This paper shows that domain-independent tools from classical planning can be used to model and solve a broad class of game-theoretic problems we call Cost-Adversarial Planning Games (CAPGs). We define CAPGs as 2-player normal-form games specified by a planning task and a finite collection of cost functions. The first player (a planning agent) strives to solve a planning task optimally but has limited knowledge about its action costs. The second player (an adversary agent) controls the actual action costs. Even though CAPGs need not be zero-sum, every CAPG has an associated zero-sum game whose Nash equilibrium provides the optimal randomized strategy for the planning agent in the original CAPG. We show how to find the Nash equilibrium of the associated zero-sum game using a cost-optimal planner via the Double Oracle algorithm. To demonstrate the expressivity of CAPGs, we formalize a patrolling security game and several IPC domains as CAPGs.

SoCS Conference 2022 Conference Paper

Urban Traffic Control via Planning with Global State Constraints (Extended Abstract)

Franc Ivankovic
Mauro Vallati
Lukás Chrpa
Marco Roveri

Planning with global state constraints is an extension of classical planning such that some properties of each state are derived via a set of rules common to all states. This approach is important for the application of planning techniques in manipulating cyber-physical systems, and has been shown to be effective in practice. Urban Traffic Control (UTC) deals with the control and management of traffic in urban regions, and includes the optimisation of traffic signals configuration to minimise traffic congestion and travel delays. In this paper, we briefly introduce how to cast the UTC problem into the formalism of planning with global state constraints, and we perform a preliminary experimental evaluation considering significant scenarios taken from the literature, and a new one based on real-world data. The results show that the approach is feasible, and the quality of generated solutions has been confirmed in simulation using existing symbolic models.

SoCS Conference 2021 Conference Paper

Adversary Strategy Sampling for Effective Plan Generation

Lukás Chrpa
Pavel Rytír
Rostislav Horcík
Jan Cuhel
Anastasiia Livochka
Stefan Edelkamp

Effective plan generation in adversarial environments has to take into account possible actions of adversary agents, i. e. , the agent should know what the competitor will likely do. In this paper we propose a novel approach for estimating strategies of the adversary, sampling actions that interfere with the agent

SoCS Conference 2020 Conference Paper

Planning Against Adversary in Zero-Sum Games: Heuristics for Selecting and Ordering Critical Actions

Lukás Chrpa
Pavel Rytír
Rostislav Horcík

Effective and efficient reasoning in adversarial environments is important for many real-world applications ranging from cybersecurity to military operations. Deliberative reasoning techniques, such as Automated Planning, often restrict to static environments where only an agent can make changes by its actions. On the other hand, such techniques are effective and can generate non-trivial solutions. To explicitly reason in environments with an active adversary such as zero-sum games, the game-theoretic framework such as the Double Oracle algorithm can be leveraged. In this paper, we leverage the notions of critical and adversary actions, where critical actions should be applied before the adversary ones. We propose heuristics that provide a guidance for planners about what (critical) actions and in which order have to be applied in a good plan. We empirically evaluate our approach in terms of quality of generated strategies (by leveraging Double Oracle) and CPU time required to generated such strategies.

SoCS Conference 2018 Conference Paper

Using Algorithm Configuration Tools to Generate Hard SAT Benchmarks

Tomás Balyo
Lukás Chrpa

Algorithm configuration tools have been successfully used to speed up local search satisfiability (SAT) solvers and other search algorithms by orders of magnitude. In this paper, we show that such tools are also very useful for generating hard SAT formulas with a planted solution, which is useful for benchmarking SAT solving algorithms and also has cryptographic applications. Our experiments with state-of-the-art local search SAT solvers show that by using this approach we can randomly generate satisfiable formulas that are considerably harder than uniform random formulas of the same size from the phase-transition region or formulas generated by state-of-the-art approaches. Additionally, we show how to generate small satisfiable formulas that are hard to solve by CDCL solvers.

SoCS Conference 2017 Conference Paper

Improving a Planner's Performance through Online Heuristic Configuration of Domain Models

Mauro Vallati
Lukás Chrpa
Thomas Leo McCluskey

The separation of planner logic from domain knowledge supports the use of reformulation and configuration techniques, such as macro-actions and entanglements, which transform the model representation in order to improve a planner’s performance. One drawback of such an approach is that it may require a potentially expensive training phase. In this paper, we introduce heuristic approaches for the online configuration of planning domain models. The proposed heuristics consider different aspects of PDDL-encoded operators for reordering such operators in the domain model, relying on the assumption that the way in which operators are encoded carries useful information about their expected use.

IROS Conference 2017 Conference Paper

Mixed-initiative planning, replanning and execution: From concept to field testing using AUV fleets

Lukás Chrpa
José Pinto 0001
Tiago Sa Marques
Manuel A. Ribeiro
João B. Sousa

Mission planning and execution for autonomous vehicles is crucial for their effective and efficient operation during scientific exploration, or search and rescue missions, to mention a few. Automated Planning has shown to be a useful tool for “high level” mission planning, that is, allocating tasks to vehicles while following given constraints (e. g. , energy, collision avoidance). In this paper, we focus on making mission planning flexible and robust. That is, a human mission coordinator can modify tasks during the mission execution, so the tasks have to be dynamically reallocated during the process. Moreover, we assume that communication might not be reliable when vehicles are “outside”, i. e. , performing the tasks, and thus we enforce vehicles to come back to their safe spots regularly. To address these requirements, we have developed two models, namely “all tasks” and “one round”, and integrated them to the control software. We have evaluated our approach in a field experiment focused on a mine-hunting scenario.

ICAPS Conference 2017 Conference Paper

On the Exploitation of Automated Planning for Reducing Machine Tools Energy Consumption between Manufacturing Operations

Simon Parkinson
Andrew Longstaff
Simon Fletcher
Mauro Vallati
Lukás Chrpa

There has recently been an increased emphasis on reducing energy consumption in manufacturing, driven by the fluctuations in energy costs and the growing importance given to environmental impact of manufactured goods. Lots of attention has been given to the reduction of machine tools energy consumption, as they require large amounts of energy to perform manufacturing tasks. One area that has received relatively little interest, yet could harness great potential, is reducing energy consumption by planning machine activities between manufacturing operations, while the machine is not in use. The intuitive option --which is currently exploited in manufacturing-- is to leave the machine in a normal operating state in anticipation of the next manufacturing job. However, this is far from optimal due to the thermal deformation phenomenon, which usually require an energy-intensive warm-up cycle in order to bring all the components (e. g. spindle motor) into a suitable (stable) state for actual machining. Evidently, the use of this strategy comes with the associated commercial and environmental repercussions. In this paper, we investigate the exploitability of automated planning techniques for planning machine activities between manufacturing operations. We present a PDDL 2. 2 formulation of the task that considers energy consumption, thermal deformation, and accuracy. We then demonstrate the effectiveness of the proposed approach using a case study which considers real-world data.

SoCS Conference 2015 Conference Paper

Exploring the Synergy between Two Modular Learning Techniques for Automated Planning

Raquel Fuentetaja 0001
Lukás Chrpa
Thomas Leo McCluskey
Mauro Vallati

In the last decade the emphasis on improving the operational performance of domain independent automated planners has been in developing complex techniques which merge a range of different strategies. This quest for operational advantage, driven by the regular international planning competitions, has not made it easy to study, understand and predict what combinations of techniques will have what effect on a planner’s behaviour in a particular application domain. In this paper, we consider two machine learning techniques for planner performance improvement, and exploit a modular approach to their combination in order to facilitate the analysis of the impact of each individual component. We believe this can contribute to the development of more transparent planning engines, which are designed using modular, interchangeable, and well-founded components. Specifically, we combined two previously unrelated learning techniques, entanglements and relational decision trees, to guide a “vanilla” search algorithm. We report on a large experimental analysis which demonstrates the effectiveness of the approach in terms of performance improvements, resulting in a very competitive planning configuration despite the use of a more modular and transparent architecture. This gives insights on the strengths and weaknesses of the considered approaches, that will help their future exploitation.

IROS Conference 2015 Conference Paper

On mixed-initiative planning and control for Autonomous underwater vehicles

Lukás Chrpa
José Pinto 0001
Manuel A. Ribeiro
Frederic Py
João B. Sousa
Kanna Rajan

Supervision and control of Autonomous underwater vehicles (AUVs) has traditionally been focused on an operator determining a priori the sequence of waypoints of a single vehicle for a mission. As AUVs become more ubiquitous as a scientific tool, we envision the need for controlling multiple vehicles which would impose less cognitive burden on the operator with a more abstract form of human-in-the-loop control. Such mixed-initiative methods in goal-oriented commanding are new for the oceanographic domain and we describe the motivations and preliminary experiments with multiple vehicles operating simultaneously in the water, using a shore-based automated planner.

SoCS Conference 2015 Conference Paper

Towards a Reformulation Based Approach for Efficient Numeric Planning: Numeric Outer Entanglements

Lukás Chrpa
Enrico Scala
Mauro Vallati

Restricting the search space has shown to be an effective approach for improving the performance of automated planning systems. A planner-independent technique for pruning the search space is domain and problem reformulation. Recently, Outer Entanglements, which are relations between planning operators and initial or goal predicates, have been introduced as a reformulation technique for eliminating potential undesirable instances of planning operators, and thus restricting the search space. Reformulation techniques, however, have been mainly applied in classical planning, although many real-world planning applications require to deal with numerical information. In this paper, we investigate the usefulness of reformulation approaches in planning with numerical fluents. In particular, we propose and extension of the notion of outer entanglements for handling numeric fluents. An empirical evaluation, which involves 150 instances from 5 domains, shows promising results.

ICAPS Conference 2014 Conference Paper

MUM: A Technique for Maximising the Utility of Macro-operators by Constrained Generation and Use

Lukás Chrpa
Mauro Vallati
Thomas Leo McCluskey

Research into techniques that reformulate problems to make general solvers more efficiently derive solutions has attracted much attention, in particular when the reformulation process is to some degree solver and domain independent. There are major challenges to overcome when applying such techniques to automated planning, however: reformulation methods such as adding macro-operators (macros, for short) can be detrimental because they tend to increase branching factors during solution search, while other methods such as learning entanglements can limit a planner's space of potentially solvable problems (its coverage) through over-pruning. These techniques may therefore work well with some domain-problem-planner combinations, but work poorly with others. In this paper we introduce a new learning technique (MUM) for synthesising macros from training example plans in order to improve the speed and coverage of domain independent automated planning engines. MUM embodies domain – independent constraints for selecting macro candidates, for generating macros, and for limiting the size of the grounding set of learned macros, therefore maximising the utility of used macros. Our empirical results with IPC benchmark domains and a range of state of the art planners demonstrate the advance that MUM makes to the increased coverage and efficiency of the planners. Comparisons with a previous leading macro learning mechanism further demonstrate MUM's capability.

SoCS Conference 2014 Conference Paper

On Different Strategies for Eliminating Redundant Actions from Plans

Tomás Balyo
Lukás Chrpa
Asma Kilani

Satisficing planning engines are often able to generate plans in a reasonable time, however, plans are often far from optimal. Such plans often contain a high number of redundant actions, that are actions, which can be removed without affecting the validity of the plans. Existing approaches for determining and eliminating redundant actions work in polynomial time, however, do not guarantee eliminating the "best" set of redundant actions, since such a problem is NP-complete. We introduce an approach which encodes the problem of determining the "best" set of redundant actions (i. e. having the maximum total-cost) as a weighted MaxSAT problem. Moreover, we adapt the existing polynomial technique which greedily tries to eliminate an action and its dependants from the plan in order to eliminate more expensive redundant actions. The proposed approaches are empirically compared to existing approaches on plans generated by state-of-the-art planning engines on standard planning benchmarks.

ECAI Conference 2012 Conference Paper

On Exploiting Structures of Classical Planning Problems: Generalizing Entanglements

Lukás Chrpa
Thomas Leo McCluskey

Much progress has been made in the research and development of automated planning algorithms in recent years. Though incremental improvements in algorithm design are still desirable, complementary approaches such as problem reformulation are important in tackling the high computational complexity of planning. While machine learning and adaptive techniques have been usefully applied to automated planning, these advances are often tied to a particular planner or class of planners that are coded to exploit that learned knowledge. A promising research direction is in exploiting knowledge engineering techniques such as reformulating the planning domain and/or the planning problem to make the problem easier to solve for general, state-of-the-art planners. Learning (outer) entanglements is one such technique, where relations between planning operators and initial or goal atoms are learned, and used to reformulate a domain by removing unneeded operator instances. Here we generalize this approach significantly to cover relations between atoms and pairs of operators themselves, and develop a technique for producing inner entanglements. We present methods for detecting inner entanglements and for using them to do problem reformulation. We provide a theoretical treatment of the area, and an empirical evaluation of the methods using standard planning benchmarks and state-of-the-art planners.

ICAPS Conference 2012 Conference Paper

Optimizing Plans through Analysis of Action Dependencies and Independencies

Lukás Chrpa
Thomas Leo McCluskey
Hugh Osborne

The problem of automated planning is known to be intractable in general. Moreover, it has been proven that in some cases finding an optimal solution is much harder than finding any solution. Existing techniques have to compromise between speed of the planning process and quality of solutions. For example, techniques based on greedy search often are able to obtain solutions quickly, but the quality of the solutions is usually low. Similarly, adding macro-operators to planning domains often enables planning speed-up, but solution sequences are typically longer. In this paper, we propose a method for optimizing plans with respect to their length, by post-planning analysis. The method is based on analyzing action dependencies and independencies by which we are able to identify redundant actions or non-optimal sub-plans. To evaluate the process we provide preliminary empirical evidence using benchmark domains.