Author name cluster

Sebastian Sardiña

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.

21 papers

2 author rows

ECAI Conference 2025 Conference Paper

On the Computational Complexity of Partial Satisfaction Planning

Jiajia Song
Seeun William Umboh
Nir Lipovetzky
Sebastian Sardiña

We analyse the computational complexity of two types of partial satisfaction planning problems, namely, over-subscription planning and net-benefit planning. Partial satisfaction planning seeks to maximise the rewards, or net-benefit between the rewards and costs, that can be obtained by achieving a set of (candidate) goals, generally under a cost budget. In this paper, we assume that the cost budget is polynomially bounded with respect to the number of atoms. In contrast to previous works on complexity analysis, we view partial satisfaction planning as optimisation tasks instead of decision ones. Accordingly, we classify over-subscription and net-benefit planning problems in classes within the optimisation complexity framework. Let L be the size of the partial satisfaction planning instance, we first show that both optimisation problems are OptP[LO(1)]-complete. We then prove that while over-subscription planning becomes OptP[O(log L)]-complete under uniform goal rewards and uniform action costs, the complexity of net-benefit planning remains unchanged. Our results show that the relative values of rewards and costs may impact the computational complexity of partial satisfaction planning, and that an optimisation perspective can reveal differences that may otherwise be lost in their decision formulations. In addition, an optimisation complexity analysis can provide insights on approximation properties of these problems.

EAAI Journal 2024 Journal Article

Adaptive goal recognition using process mining techniques

Zihang Su
Artem Polyvyanyy
Nir Lipovetzky
Sebastian Sardiña
Nick van Beest

Goal Recognition (GR) is a research problem that studies ways to infer the goal of an intelligent agent based on its observed behavior and knowledge of the environment in which the agent operates. A common assumption of GR is that the environment is static. However, in many real-world scenarios, for example, recognizing customers’ preferences, it is necessary to recognize the goals of multiple agents or multiple goals of a single agent over an extended period. Therefore, it is reasonable to expect the environment to change throughout a series of goal recognition tasks. This paper presents three process mining-based solutions to the problem of adaptive GR in a changing environment implemented as different control strategies of a system for solving standard GR problems. As a standard GR system that gets controlled, we use the system grounded in process mining techniques, as it can adjust its internal GR mechanisms based on data collected while observing the operating agents. We evaluated our control strategies over synthetic and real-world datasets. The synthetic datasets were generated using the extended version of the Goal Recognition Amidst Changing Environments (GRACE) tool. The datasets account for different types of changes and drifts in the environment. The evaluation results demonstrate a trade-off between the GR performance over time and the effort invested in adaptations of the GR mechanisms of the system, showing that few well-planned adaptations can lead to a consistently high GR performance.

ECAI Conference 2023 Conference Paper

A Declarative Approach to Compact Controllers for FOND Planning via Answer Set Programming

Nitin Yadav
Sebastian Sardiña

We present an approach to non-deterministic planning under full observability via Answer Set Programming. The technique can synthesise compact policies, handle both fair and unfair actions simultaneously, and readily accommodate control knowledge and procedural domain constraints. We show that whereas compact controllers may yield sub-optimal behavior under a naive executor, optimality can be recovered under a smarter executor. The developed planner is succinct, elegant, and directly implementable, thus providing higher confidence of its correctness and ease of elaboration. Experimental results show that its performance is competitive.

AIJ Journal 2023 Journal Article

Fast and accurate data-driven goal recognition using process mining techniques

Zihang Su
Artem Polyvyanyy
Nir Lipovetzky
Sebastian Sardiña
Nick van Beest

The problem of goal recognition requests to automatically infer an accurate probability distribution over possible goals an autonomous agent is attempting to achieve in the environment. The state-of-the-art approaches for goal recognition operate under full knowledge of the environment and possible operations the agent can take. This knowledge, however, is often not available in real-world applications. Given historical observations of the agents' behaviors in the environment, we learn skill models that capture how the agents achieved the goals in the past. Next, given fresh observations of an agent, we infer their goals by diagnosing deviations between the observations and all the available skill models. We present a framework that serves as an outline for implementing such data-driven goal recognition systems and its instance system implemented using process mining techniques. The evaluations we conducted using our publicly available implementation confirm that the approach is well-defined, i. e. , all system parameters impact its performance, has high accuracy over a wide range of synthetic and real-world domains, which is comparable with the more knowledge-demanding state-of-the-art approaches, and operates fast.

AIJ Journal 2022 Journal Article

Situation calculus for controller synthesis in manufacturing systems with first-order state representation

Giuseppe De Giacomo
Paolo Felli
Brian Logan
Fabio Patrizi
Sebastian Sardiña

Manufacturing is transitioning from a mass production model to a service model in which facilities ‘bid’ to produce products. To decide whether to bid for a complex, previously unseen product, a facility must be able to synthesize, on the fly, a process plan controller that delegates abstract manufacturing tasks in a supplied process recipe to the available manufacturing resources. Often manufacturing processes depend on the data and objects (parts) they produce and consume. To formalize this aspect we need to adopt a first-order representation of the state of the processes. First-order representations of the state are commonly considered in reasoning about action in AI, and here we show that we can leverage the wide literature on the Situation Calculus and ConGolog programs to formalize this kind of manufacturing. With such a formalization available, we investigate how to synthesize process plan controllers in this first-order state setting. We also identify two important decidable cases—finite domains and bounded action theories—for which we provide techniques to actually synthesize the controller.

IJCAI Conference 2022 Conference Paper

Situation Calculus for Controller Synthesis in Manufacturing Systems with First-Order State Representation (Extended Abstract)

Giuseppe De Giacomo
Paolo Felli
Brian Logan
Fabio Patrizi
Sebastian Sardiña

Manufacturing is transitioning from a mass production model to a service model in which facilities `bid' for previously unseen products. To decide whether to bid for a previously unseen product, a facility must be able to synthesize, on the fly, a process plan controller that delegates abstract manufacturing tasks in a supplied process recipe to the available manufacturing resources. First-order representations of the state are commonly considered in reasoning about action in AI. Here we show that we can leverage the wide literature on the Situation Calculus automatically synthesize such controllers. We identify two important decidable cases---finite domains and bounded action theories---for which we provide practical synthesis techniques.

PDF Details DOI

ICAPS Conference 2021 Conference Paper

Flexible FOND Planning with Explicit Fairness Assumptions

Ivan D. Rodriguez
Blai Bonet
Sebastian Sardiña
Hector Geffner

We consider the problem of reaching a propositional goal condition in fully-observable non-deterministic (FOND) planning under a general class of fairness assumptions that are given explicitly. The fairness assumptions are of the form A/B and say that state trajectories that contain infinite occurrences of an action a from A in a state s and finite occurrence of actions from B, must also contain infinite occurrences of action a in s followed by each one of its possible outcomes. The infinite trajectories that violate this condition are deemed as unfair, and the solutions are policies for which all the fair trajectories reach a goal state. We show that strong and strong-cyclic FOND planning, as well as QNP planning, a planning model introduced recently for generalized planning, are all special cases of FOND planning with fairness assumptions of this form which can also be combined. FOND+ planning, as this form of planning is called, combines the syntax of FOND planning with some of the versatility of LTL for expressing fairness constraints. A new planner is implemented by reducing FOND+ planning to answer set programs, and the performance of the planner is evaluated in comparison with FOND and QNP planners, and LTL synthesis tools.

ECAI Conference 2020 Conference Paper

Is Hardness Inherent in Computational Problems? Performance of Human and Electronic Computers on Random Instances of the 0-1 Knapsack Problem

Nitin Yadav
Carsten Murawski
Sebastian Sardiña
Peter Bossaerts

Many cognitive problems people face have been shown to be computationally intractable. However, tractability is typically defined in terms of asymptotic worst-case behaviour of instances. One approach for studying typical cases of NP-complete problems is based on random instances. It has been shown that random instances of many NP-complete problems exhibit a phase transition in solvability and that hard instances tend to occur in this phase transition. Here, we characterise a phase transition in solvability for random instances of the 0-1 knapsack problem in terms of two simple instance properties. Subsequently, we show that compute time of algorithms peaks in the phase transition. Remarkably, the phase transition likewise predicts where people spend the most effort. Nevertheless, their performance decreases. This suggests that instances that are difficult for electronic computers are recognized as such by people, but the increased effort does not compensate for hardness. Given the ubiquity of the knapsack problem in every-day life, a better characterisation of the properties that make instances hard will help understand commonalities and differences in computation between human and digital computers, and to improve both decision environments (contracts, regulation) as well as human-computer interfaces.

ICAPS Conference 2020 Conference Paper

Multi-Tier Automated Planning for Adaptive Behavior

Daniel Alfredo Ciolek
Nicolás D'Ippolito
Alberto Pozanco
Sebastian Sardiña

A planning domain, as any model, is never “complete” and inevitably makes assumptions on the environment's dynamic. By allowing the specification of just one domain model, the knowledge engineer is only able to make one set of assumptions, and to specify a single objective-goal. Borrowing from work in Software Engineering, we propose a multi-tier framework for planning that allows the specification of different sets of assumptions, and of different corresponding objectives. The framework aims to support the synthesis of adaptive behavior so as to mitigate the intrinsic risk in any planning modeling task. After defining the multi-tier planning task and its solution concept, we show how to solve problem instances by a succinct compilation to a form of non-deterministic planning. In doing so, our technique justifies the applicability of planning with both fair and unfair actions, and the need for more efforts in developing planning systems supporting dual fairness assumptions.

ICAPS Conference 2018 Conference Paper

Plan Relaxation via Action Debinding and Deordering

Max Waters
Bernhard Nebel
Lin Padgham
Sebastian Sardiña

While seminal work has studied the problem of relaxing the ordering of a plan’s actions, less attention has been given to the problem of relaxing and modifying a plan’s variable bindings. This paper studies the problem of relaxing a plan into a partial plan which specifies which operators must be executed, but need not completely specify their order or variable bindings. While partial plans can provide an agent with additional flexibility and robustness at execution time, many operations over partial plans are intractable. This paper tackles this problem by proposing and empirically evaluating a fixed-parameter tractable algorithm which searches for tractable, flexible partial plans.

ICAPS Conference 2016 Conference Paper

Computing Trace Alignment against Declarative Process Models through Planning

Giuseppe De Giacomo
Fabrizio Maria Maggi
Andrea Marrella
Sebastian Sardiña

Process mining techniques aim at extracting non-trivial knowledge from event traces, which record the concrete execution of business processes. Typically, traces are "dirty" and contain spurious events or miss relevant events. Trace alignment is the problem of cleaning such traces against a process specification. There has recently been a growing use of declarative process models, e. g. , Declare (based on LTL over finite traces) to capture constraints on the allowed task flows. We demonstrate here how state-of-the-art classical planning technologies can be used for trace alignment by presenting a suitable encoding. We report experimental results using a real log from a financial domain.

ECAI Conference 2016 Conference Paper

Summary Information for Reasoning About Hierarchical Plans

Lavindra de Silva
Sebastian Sardiña
Lin Padgham

Hierarchically structured agent plans are important for efficient planning and acting, and they also serve (among other things) to produce "richer" classical plans, composed not just of a sequence of primitive actions, but also "abstract" ones representing the supplied hierarchies. A crucial step for this and other approaches is deriving precondition and effect "summaries" from a given plan hierarchy. This paper provides mechanisms to do this for more pragmatic and conventional hierarchies than in the past. To this end, we formally define the notion of a precondition and an effect for a hierarchical plan; we present data structures and algorithms for automatically deriving this information; and we analyse the properties of the presented algorithms. We conclude the paper by detailing how our algorithms may be used together with a classical planner in order to obtain abstract plans.

ICAPS Conference 2014 Conference Paper

Building Virtual Behaviors from Partially Controllable Available Behaviors in Nondeterministic Environments

Giuseppe De Giacomo
Fabio Patrizi
Sebastian Sardiña

The composition problem involves how to coordinate a set of available modules (e. g. , concrete devices installed in a smart house, such as video cameras, lights, blinds, etc.) so as to implement a desired but non-existent target complex component (e. g. , a complex entertainment house system). This paper summarizes the results in (De Giacomo, Patrizi, and Sardina 2013), by formally defining the problem within an AI context, characterizing its complexity, and identifying effective techniques to solve it. Related results are also briefly discussed.

ICAPS Conference 2014 Conference Paper

Directed Fixed-Point Regression-Based Planning for Non-Deterministic Domains

Miquel Ramírez
Sebastian Sardiña

We present a novel approach to fully-observable nondeterministic planning (FOND) that attempts to bridge the gap between symbolic fix-point computation and recent approaches based on forward heuristic search. Concretely, we formalize the relationship between symbolic and dynamic programming nondeterministic planners, and then exploit such connection to propose a novel familyof planning algorithms that reasons over symbolic policies in a directed manner. By doing so, our proposal reasons over sets of states and executions in a succinct way (as done by symbolic planners) while biasing the reasoning with respect to the initial and goal states of the specific planning problem at hand (as done by heuristic planners). We show empirical results that prove this approach promising in settings where there is an intrinsic tension between plan efficiency and plan "robustness, " a feature to be expected in nondeterministic domains.

AIJ Journal 2013 Journal Article

Automatic behavior composition synthesis

Giuseppe De Giacomo
Fabio Patrizi
Sebastian Sardiña

The behavior composition problem amounts to realizing a virtual desired module (e. g. , a surveillance agent system) by suitably coordinating (and re-purposing) the execution of a set of available modules (e. g. , a video camera, vacuum cleaner, a robot, etc.). In particular, we investigate techniques to synthesize a controller implementing a fully controllable target behavior by suitably coordinating available partially controllable behaviors that are to execute within a shared, fully observable, but partially predictable (i. e. , non-deterministic), environment. Both behaviors and environment are represented as arbitrary finite state transition systems. The technique we propose is directly based on the idea that the controller job is to coordinate the concurrent execution of the available behaviors so as to “mimic” the target behavior. To this end, we exploit a variant of the formal notion of simulation to formally capture the notion of “mimicking”, and we show that the technique proposed is sound and complete, optimal with respect to computational complexity, and robust for different kind of system failures. In addition, we demonstrate that the technique is well suited for highly efficient implementation based on synthesis by model checking technologies, by relating the problem to that of finding a winning strategy in a special safety game and explaining how to actually solve it using an existing verification tool.

ICAPS Conference 2013 Conference Paper

Behavior Composition as Fully Observable Non-Deterministic Planning

Miquel Ramírez
Nitin Yadav
Sebastian Sardiña

The behavior composition problem involves the automatic synthesis of a controller able to “realize” (i. e. , implement) a target behavior module by suitably coordinating a collection of partially controllable available behaviors. In this paper, we show that the existence of a composition solution amounts to finding a strong cyclic plan for a special non-deterministic planning problem, thus establishing the formal link between the two synthesis tasks. Importantly, our results support the use of non-deterministic planing systemsfor solving composition problems in an off-the-shelf manner. We then empirically evaluate three state-of-the-art synthesis systems (a domain-independent automated planner and two game solvers based on model checking techniques) on various non-trivial composition instances. Our experiments show that while behavior composition is EXPTIME-complete, the current technology is already able to handle instances of significant complexity. Our work is, as far as we know, the first serious experimental work on behavior composition.

JELIA Conference 2012 Conference Paper

Qualitative Approximate Behavior Composition

Nitin Yadav
Sebastian Sardiña

Abstract The behavior composition problem involves automatically building a controller that is able to realize a desired, but unavailable, target system (e. g. , a house surveillance) by suitably coordinating a set of available components (e. g. , video cameras, blinds, lamps, a vacuum cleaner, phones, etc.) Previous work has almost exclusively aimed at bringing about the desired component in its totality, which is highly unsatisfactory for unsolvable problems. In this work, we develop an approach for approximate behavior composition without departing from the classical setting, thus making the problem applicable to a much wider range of cases. Based on the notion of simulation, we characterize what a maximal controller and the “closest” implementable target module (optimal approximation) are, and show how these can be computed using ATL model checking technology for a special case. We show the uniqueness of optimal approximations, and prove their soundness and completeness with respect to their imported controllers.

JELIA Conference 2012 Conference Paper

Reasoning about Agent Programs Using ATL-Like Logics

Nitin Yadav
Sebastian Sardiña

Abstract We propose a variant of Alternating-time Temporal Logic (ATL) grounded in the agents’ operational know-how, as defined by their libraries of abstract plans. Inspired by ATLES, a variant itself of ATL, it is possible in our logic to explicitly refer to “rational” strategies for agents developed under the Belief-Desire-Intention agent programming paradigm. This allows us to express and verify properties of BDI systems using ATL-type logical frameworks.

ICAPS Conference 2009 Conference Paper

Optimality Properties of Planning Via Petri Net Unfolding: A Formal Analysis

Sarah L. Hickmott
Sebastian Sardiña

We provide a theoretical analysis of planning via Petri net unfolding, a novel technique for synthesising parallel plans. Parallel plans are generally valued for their execution ﬂexi- bility, which manifests as alternative choices for the order- ing of operators and potentially faster plan executions. Being a relatively new approach, the ﬂexibility properties of plans synthesised via unfolding, and even the concurrency seman- tics supported by this technique, are particularly unclear and only understood at an informal level. In this paper, we ﬁrst formally characterise the concurrency semantics of planning via unfolding as a further restriction on the standard notion of independence. More importantly, we then prove that plans obtained using this approach are optimal deorderings and op- timal reorderings in terms of the number of ordering con- straints on operators and plan execution time, respectively. These results provide objective guarantees on the quality of plans obtained by the unfolding technique.

ICAPS Conference 2008 Conference Paper

Realizing Multiple Autonomous Agents through Scheduling of Shared Devices

Sebastian Sardiña
Giuseppe De Giacomo

Imagine a collection of available devices, such as a camera, a vacuum cleaner, or robotic arm, each of which is able to act (that is, perform actions) according to a given behavior specification, expressed as a finite transition system. Imagine next a set of virtual independent and autonomous agents, such as a surveillance agent or a cleaning agent, which are meant to operate concurrently, each within a given specification of its capabilities, again expressed as a finite transition system. The question then is: can we guarantee the realization of every agent by intelligently scheduling the available devices while fully preserving the agents' autonomy? In this paper, we define the problem formally, and propose a technique to actually generate a solution by appealing to recent results in LTL-based synthesis of reactive systems. We also show that the proposed technique is optimal with respect to computational complexity.

LPAR Conference 2001 Conference Paper

Local Conditional High-Level Robot Programs

Sebastian Sardiña

Abstract When it comes to buildingrob ot controllers, high-level programming arises as a feasible alternative to planning. The task then is to verify a high-level program by finding a legal execution of it. However, interleaving offline verification with execution in the world seems to be the most practical approach for large programs and complex scenarios involvinginformation gatheringand exogenous events. In this paper, we present a mechanism for performing local lookahead for the Golog family of high-level robot programs. The main features of such mechanism are that it takes sensing seriously by constructing conditional plans that are ready to be executed in the world, and it mixes perfectly with an account of interleaved perception, planning, and action. Also, a simple implementation is developed.