Daniel Borrajo

JAAMAS Journal 2026 Journal Article

Intelligent Travel Planning: A MultiAgent Planning System to Solve Web Problems in the e-Tourism Domain

• David Camacho
• Daniel Borrajo
• Jose M. Molina

Abstract This paper presents Intelligent Travel Planning (ITP), a multiagent planning system to solve Web electronic problems in the Web, whose main goal is to search for useful solutions in the electronic-Tourism domain to system users. The system uses different types of intelligent autonomous agents whose main characteristics are cooperation, negotiation, learning, planning and knowledge sharing. Obviously the information used by the intelligent agents is heterogeneous and geographically distributed, since the main information source of the system is Internet. Other information sources are agent knowledge bases in the distributed system. The process to obtain, filter, and store the information is performed automatically by agents. This information is translated into a homogeneous format for high-level reasoning in order to obtain different partial solutions. Partial solutions are reconstructed into a general solution (or solutions) to be presented to the user. The system will show a set of solutions to the users that can be evaluated by them.

KR Conference 2025 Conference Paper

A Planning Compilation to Reason About Goal Achievement at Planning Time

• Alberto Pozanco
• Marianela Morales
• Daniel Borrajo
• Manuela Veloso

Identifying the specific actions that achieve goals when solving a planning task might be beneficial for various planning applications. Traditionally, this identification occurs post-search, as some actions may temporarily achieve goals that are later undone and re-achieved by other actions. In this paper, we propose a compilation that extends the original planning task with commit actions that enforce the persistence of specific goals once achieved, allowing planners to identify permanent goal achievement during planning. Experimental results indicate that solving the reformulated tasks does not incur on any additional overhead both when performing optimal and suboptimal planning, while providing useful information for some downstream tasks.

ECAI Conference 2025 Conference Paper

On Learning Action Costs from Input Plans

• Marianela Morales
• Alberto Pozanco
• Giuseppe Canonaco
• Sriram Gopalakrishnan
• Daniel Borrajo
• Manuela Veloso

Most of the work on learning action models focus on learning the actions’ dynamics from input plans. This allows us to specify the valid plans of a planning task. However, very little work focuses on learning action costs, which in turn allows us to rank the different plans. In this paper we introduce a new problem: that of learning the costs of a set of actions such that a set of input plans are optimal under the resulting planning model. To solve this problem we present LACFIPk, an algorithm to learn action’s costs from unlabeled input plans. We provide theoretical and empirical results showing how LACFIPk can successfully solve this task.

ECAI Conference 2025 Conference Paper

On the Sample Efficiency of Abstractions and Potential-Based Reward Shaping in Reinforcement Learning

• Giuseppe Canonaco
• Leo Ardon
• Alberto Pozanco
• Daniel Borrajo

The use of Potential-Based Reward Shaping (PBRS) has shown great promise in the ongoing research effort to tackle sample inefficiency in Reinforcement Learning (RL). However, choosing the right potential function remains an open challenge. Additionally, RL techniques are usually constrained to use a finite horizon for computational limitations, which introduces a bias when using PBRS. In this paper, we first build some theoretically-grounded intuition on why selecting the potential function as the optimal value function of the task at hand produces performance advantages. We then analyse the bias induced by finite horizons in the context of PBRS producing novel insights. Finally, leveraging abstractions as a way to approximate the optimal value function of the given task, we assess the sample efficiency and performance impact of PBRS on four environments including a goal-oriented navigation task and three Arcade Learning Environments (ALE) games. Remarkably, experimental results show that we can reach the same level of performance as CNN-based solutions with a simple fully-connected network.

ECAI Conference 2025 Conference Paper

The Subset Sum Matching Problem

• Yufei Wu 0012
• Manuel R. Torres
• Parisa Zehtabi
• Alberto Pozanco
• Michael Cashmore
• Daniel Borrajo
• Manuela Veloso

This paper presents a new combinatorial optimisation task, the Subset Sum Matching Problem (SSMP), which is an abstraction of common financial applications such as trades reconciliation. We present three algorithms, two suboptimal and one optimal, to solve this problem. We also generate a benchmark to cover different instances of SSMP varying in complexity, and carry out an experimental evaluation to assess the performance of the approaches.

ICAPS Conference 2024 Conference Paper

Computing Planning Centroids and Minimum Covering States Using Symbolic Bidirectional Search

• Alberto Pozanco
• Álvaro Torralba
• Daniel Borrajo

In some scenarios, planning agents might be interested in reaching states that keep certain relationships with respect to a set of goals. Recently, two of these types of states were proposed: centroids, which minimize the average distance to the goals; and minimum covering states, which minimize the maximum distance to the goals. Previous approaches compute these states by searching forward either in the original or a reformulated task. In this paper, we propose several algorithms that use symbolic bidirectional search to efficiently compute centroids and minimum covering states. Experimental results in existing and novel benchmarks show that our algorithms scale much better than previous approaches, establishing a new state-of-the-art technique for this problem.

ICAPS Conference 2024 Conference Paper

Contrastive Explanations of Centralized Multi-agent Optimization Solutions

• Parisa Zehtabi
• Alberto Pozanco
• Ayala Bolch
• Daniel Borrajo
• Sarit Kraus

In many real-world scenarios, agents are involved in optimization problems. Since most of these scenarios are over-constrained, optimal solutions do not always satisfy all agents. Some agents might be unhappy and ask questions of the form “Why does solution S not satisfy property P? ”. We propose CMAOE, a domain-independent approach to obtain contrastive explanations by: (i) generating a new solution S′ where property P is enforced, while also minimizing the differences between S and S′; and (ii) highlighting the differences between the two solutions, with respect to the features of the objective function of the multi-agent system. Such explanations aim to help agents understanding why the initial solution is better in the context of the multi-agent system than what they expected. We have carried out a computational evaluation that shows that CMAOE can generate contrastive explanations for large multi-agent optimization problems. We have also performed an extensive user study in four different domains that shows that: (i) after being presented with these explanations, humans’ satisfaction with the original solution increases; and (ii) the constrastive explanations generated by CMAOE are preferred or equally preferred by humans over the ones generated by state of the art approaches.

AAAI Conference 2024 Conference Paper

Generalising Planning Environment Redesign

• Alberto Pozanco
• Ramon Fraga Pereira
• Daniel Borrajo

In Environment Design, one interested party seeks to affect another agent's decisions by applying changes to the environment. Most research on planning environment (re)design assumes the interested party's objective is to facilitate the recognition of goals and plans, and search over the space of environment modifications to find the minimal set of changes that simplify those tasks and optimise a particular metric. This search space is usually intractable, so existing approaches devise metric-dependent pruning techniques for performing search more efficiently. This results in approaches that are not able to generalise across different objectives and/or metrics. In this paper, we argue that the interested party could have objectives and metrics that are not necessarily related to recognising agents' goals or plans. Thus, to generalise the task of Planning Environment Redesign, we develop a general environment redesign approach that is metric-agnostic and leverages recent research on top-quality planning to efficiently redesign planning environments according to any interested party's objective and metric. Experiments over a set of environment redesign benchmarks show that our general approach outperforms existing approaches when using well-known metrics, such as facilitating the recognition of goals, as well as its effectiveness when solving environment redesign tasks that optimise a novel set of different metrics.

HAXP Workshop 2024 Workshop Paper

On Computing Plans with Uniform Action Costs

• Alberto Pozanco
• Daniel Borrajo
• Manuela Veloso

In many real-world planning applications, agents might be interested in finding plans whose actions have costs that are as uniform as possible. Such plans provide agents with a sense of stability and predictability, which are key features when humans are the agents executing plans suggested by planning tools. This paper adapts three uniformity metrics to automated planning, and introduce planning-based compilations that allow to lexicographically optimize sum of action costs and action costs uniformity. Experimental results both in well-known and novel planning benchmarks show that the reformulated tasks can be effectively solved in practice to generate uniform plans.

ICAPS Conference 2023 Conference Paper

Combining Heuristic Search and Linear Programming to Compute Realistic Financial Plans

• Alberto Pozanco
• Kassiani Papasotiriou
• Daniel Borrajo
• Manuela Veloso

Defining financial goals and formulating actionable plans to achieve them are essential components for ensuring financial health. This task is computationally challenging, given the abundance of factors that can influence one’s financial situation. In this paper, we present the Personal Finance Planner (PFP), which can generate personalized financial plans that consider a person’s context and the likelihood of taking financially related actions to help them achieve their goals. PFP solves the problem in two stages. First, it uses heuristic search to find a high-level sequence of actions that increase the income and reduce spending to help users achieve their financial goals. Next, it uses integer linear programming to determine the best low-level actions to implement the high-level plan. Results show that PFP is able to scale on generating realistic financial plans for complex tasks involving many low level actions and long planning horizons.

ECAI Conference 2023 Conference Paper

Generating Replanning Goals Through Multi-Objective Optimization in Response to Execution Observation

• Alberto Pozanco
• Daniel Borrajo
• Manuela Veloso

In some applications, planning-monitoring systems generate plans and monitor their execution by other agents. During execution, agents might deviate from these plans for various reasons. The deviation from the expected behavior will be observed by the planning-monitoring system, which will replan in order to provide the agent a new suggested plan. Most existing replanning approaches maintain the goals and compute a plan that achieves them under the new circumstances. This is often not realistic, as achieving the original goal might be very costly or impossible under the current conditions. Furthermore, replanning approaches usually overlook agent’s behavior up to the observed deviation from the original plan. In this paper we introduce GREPLAN, a novel approach that proposes new replanning goals (and plans) by solving a multi-objective optimization problem that considers all goals within a perimeter of the original goal. Empirical results in several planning benchmarks show that GREPLAN successfully reacts to deviations from the original plan by generating new appropriate replanning goals.

PRL Workshop 2023 Workshop Paper

Inapplicable Actions Learning for Knowledge Transfer in Reinforcement Learning

• Leo Ardon
• Alberto Pozanco
• Daniel Borrajo
• Sumitra Ganesh

Reinforcement Learning (RL) algorithms are known to scale poorly to environments with many available actions, requiring numerous samples to learn an optimal policy. The traditional approach of considering the same fixed action space in every possible state implies that the agent must understand, while also learning to maximize its reward, to ignore irrelevant actions such as $\textit{inapplicable actions}$ (i.e. actions that have no effect on the environment when performed in a given state). Knowing this information can help reduce the sample complexity of RL algorithms by masking the inapplicable actions from the policy distribution to only explore actions relevant to finding an optimal policy. While this technique has been formalized for quite some time within the Automated Planning community with the concept of precondition in the STRIPS language, RL algorithms have never formally taken advantage of this information to prune the search space to explore. This is typically done in an ad-hoc manner with hand-crafted domain logic added to the RL algorithm. In this paper, we propose a more systematic approach to introduce this knowledge into the algorithm. We (i) standardize the way knowledge can be manually specified to the agent; and (ii) present a new framework to autonomously learn the partial action model encapsulating the precondition of an action jointly with the policy. We show experimentally that learning inapplicable actions greatly improves the sample efficiency of the algorithm by providing a reliable signal to mask out irrelevant actions. Moreover, we demonstrate that thanks to the transferability of the knowledge acquired, it can be reused in other tasks and domains to make the learning process more efficient.

NeurIPS Conference 2023 Conference Paper

On the Constrained Time-Series Generation Problem

• Andrea Coletta
• Sriram Gopalakrishnan
• Daniel Borrajo
• Svitlana Vyetrenko

Synthetic time series are often used in practical applications to augment the historical time series dataset, amplify the occurrence of rare events and also create counterfactual scenarios. Distributional-similarity (which we refer to as realism) as well as the satisfaction of certain numerical constraints are common requirements for counterfactual time series generation. For instance, the US Federal Reserve publishes synthetic market stress scenarios given by the constrained time series for financial institutions to assess their performance in hypothetical recessions. Existing approaches for generating constrained time series usually penalize training loss to enforce constraints, and reject non-conforming samples. However, these approaches would require re-training if we change constraints, and rejection sampling can be computationally expensive, or impractical for complex constraints. In this paper, we propose a novel set of methods to tackle the constrained time series generation problem and provide efficient sampling while ensuring the realism of generated time series. In particular, we frame the problem using a constrained optimization framework and then we propose a set of generative methods including 'GuidedDiffTime', a guided diffusion model. We empirically evaluate our work on several datasets for financial and energy data, where incorporating constraints is critical. We show that our approaches outperform existing work both qualitatively and quantitatively, and that 'GuidedDiffTime' does not require re-training for new constraints, resulting in a significant carbon footprint reduction, up to 92% w. r. t. existing deep learning methods.

EUMAS Conference 2022 Conference Paper

Advising Agent for Service-Providing Live-Chat Operators

• Aviram Aviv
• Yaniv Oshrat
• Samuel Assefa
• Toby Mustapha
• Daniel Borrajo
• Manuela Veloso
• Sarit Kraus

Abstract Call centers, in which human operators attend clients using textual chat, are very common in modern e-commerce. Training enough skilled operators who are able to provide good service is a challenge. We propose a methodology for the development of an assisting agent that provides online advice to operators while they attend clients. The agent is easy-to-build and can be introduced to new domains without major effort in design, training and organizing sknowledge of the professional discipline. We demonstrate the applicability of the system in an experiment that realizes its full life-cycle on a specific domain, and analyze its capabilities.

AAMAS Conference 2022 Conference Paper

Advising Agent for Service-Providing Live-Chat Operators

• Aviram Aviv
• Yaniv Oshrat
• Samuel Assefa
• Toby Mustapha
• Daniel Borrajo
• Manuela Veloso
• Sarit Kraus

Call centers, in which human operators attend clients using textual chat, are very common in modern e-commerce. Training enough skilled operators who are able to provide good service is a challenge. We propose a methodology for the development of an assisting agent that provides online advice to operators while they attend clients. The agent is easy-to-build and can be introduced to new domains without major effort in design, training and organizing structured knowledge of the professional discipline. We demonstrate the applicability of the system in an experiment that realizes its full life-cycle on a specific domain, and analyze its capabilities.

ICAPS Conference 2022 Conference Paper

Assignment and Prioritization of Tasks with Uncertain Durations for Satisfying Makespans in Decentralized Execution

• Sriram Gopalakrishnan
• Daniel Borrajo

Task assignment under execution uncertainty and temporal/resource constraints is a standard problem for many organizations. Existing approaches in the AI planning & scheduling and operations research literature predominantly focus on dynamic controllability, and non-preemptive execution of tasks. Such solutions are appropriate for teams of agents under tight control requirements. However, in most organizations with human teams, once tasks have been assigned, humans tend to execute their assignments without a constant central oversight (which is needed for dynamic controllability). In this paper we define a problem in which execution of tasks is distributed (without central oversight), and assumes humans can preempt their tasks when other tasks of higher priority are ready to be worked on. We present two algorithms based on Tabu search and Monte Carlo Tree Search to assign and prioritize tasks for such problems. Experimental results show the improved efficacy of these approaches for this problem setting over non-preemptive strategies.

ICAPS Conference 2021 Conference Paper

Computing Opportunities to Augment Plans for Novel Replanning during Execution

• Daniel Borrajo
• Manuela Veloso

Traditionally, planning provides for execution plans as sequences of actions with preconditions and effects. Execution monitoring identifies failure conditions when the preconditions of an action do not match the state. Interestingly, planning proceeds by consuming a given initial state and abandoning reasoning about any facts not true in that state. In this paper, we define opportunities as such missing facts, and contribute an algorithm to compute them and augment a plan for execution with them. We then introduce a new execution opportunity monitoring that focusedly checks for these opportunities at each execution state. Opportunistic replanning proceeds now from the new state including the detected opportunities.

IROS Conference 2021 Conference Paper

Intelligent Execution through Plan Analysis

• Daniel Borrajo
• Manuela Veloso

Intelligent robots need to generate and execute plans. In order to deal with the complexity of real environments, planning makes some assumptions about the world. When executing plans, the assumptions are usually not met. Most works have focused on the negative impact of this fact and the use of replanning after execution failures. Instead, we focus on the positive impact, or opportunities to find better plans. When planning, the proposed technique finds and stores those opportunities. Later, during execution, the monitoring system can use them to focus perception and repair the plan, instead of replanning from scratch. Experiments in several paradigmatic robotic tasks show how the approach outperforms standard replanning strategies.

AIJ Journal 2021 Journal Article

Selecting goals in oversubscription planning using relaxed plans

• Angel García-Olaya
• Tomás de la Rosa
• Daniel Borrajo

Planning deals with the task of finding an ordered set of actions that achieves some goals from an initial state. In many real-world applications it is unfeasible to find a plan achieving all goals due to limitations in the available resources. A common case consists of having a bound on a given cost measure that is less than the optimal cost needed to achieve all goals. Oversubscription planning (OSP) is the field of Automated Planning dealing with such kinds of problems. Usually, OSP generates plans that achieve only a subset of the goals set. In this paper we present a new technique to a priori select goals in no-hard-goals satisficing OSP by searching in the space of subsets of goals. A key property of the proposed approach is that it is planner-independent once the goals have been selected; it creates a new non-OSP problem that can be solved using off-the-shelf planners. Extensive experimental results show that the proposed approach outperforms state-of-the-art OSP techniques in several domains of the International Planning Competition.

SoCS Conference 2019 Conference Paper

Error Analysis and Correction for Weighted A*'s Suboptimality

• Robert C. Holte
• Rubén Majadas
• Alberto Pozanco
• Daniel Borrajo

Weighted A* (wA*) is a widely used algorithm for rapidly, but suboptimally, solving planning and search problems. The cost of the solution it produces is guaranteed to be at most W times the optimal solution cost, where W is the weight wA* uses in prioritizing open nodes. W is therefore a suboptimality bound for the solution produced by wA*. There is broad consensus that this bound is not very accurate, that the actual suboptimality of wA*

ICAPS Conference 2019 Conference Paper

Finding Centroids and Minimum Covering States in Planning

• Alberto Pozanco
• Yolanda E-Martín
• Susana Fernández
• Daniel Borrajo

In automated planning, the most common task consists of finding a plan that achieves a set of goals. In this paper, we focus on a different task; that of finding states that minimize some goal-related metric. First, we present some domains for which that task is useful. Second, we propose two of such types of states: (1) centroid states, which minimize the distance to all the goals in the problem; and (2) minimum covering states, which minimize the maximum distance to any of the goals. Third, we define optimal and suboptimal algorithms to find such states. Finally, we show some experimental results in planning instances from different domains.

IJCAI Conference 2019 Conference Paper

Guarantees for Sound Abstractions for Generalized Planning

• Blai Bonet
• Raquel Fuentetaja
• Yolanda E-Martín
• Daniel Borrajo

Generalized planning is about finding plans that solve collections of planning instances, often infinite collections, rather than single instances. Recently it has been shown how to reduce the planning problem for generalized planning to the planning problem for a qualitative numerical problem; the latter being a reformulation that simultaneously captures all the instances in the collection. An important thread of research thus consists in finding such reformulations, or abstractions, automatically. A recent proposal learns the abstractions inductively from a finite and small sample of transitions from instances in the collection. However, as in all inductive processes, the learned abstraction is not guaranteed to be correct for the whole collection. In this work we address this limitation by performing an analysis of the abstraction with respect to the collection, and show how to obtain formal guarantees for generalization. These guarantees, in the form of first-order formulas, may be used to 1) define subcollections of instances on which the abstraction is guaranteed to be sound, 2) obtain necessary conditions for generalization under certain assumptions, and 3) do automated synthesis of complex invariants for planning problems. Our framework is general, it can be extended or combined with other approaches, and it has applications that go beyond generalized planning.

IJCAI Conference 2018 Conference Paper

Counterplanning using Goal Recognition and Landmarks

• Alberto Pozanco
• Yolanda E-Martín
• Susana Fernández
• Daniel Borrajo

In non-cooperative multi-agent systems, agents might want to prevent the opponents from achieving their goals. One alternative to solve this task would be using counterplanning to generate a plan that allows an agent to block other's to reach their goals. In this paper, we introduce a fully automated domain-independent approach for counterplanning. It combines; goal recognition to infer an opponent's goal; landmarks' computation to identify subgoals that can be used to block opponents' goals achievement; and classical automated planning to generate plans that prevent the opponent's goals achievement. Experimental results in several domains show the benefits of our novel approach.

AAAI Conference 2018 Conference Paper

Meta-Search Through the Space of Representations and Heuristics on a Problem by Problem Basis

• Raquel Fuentetaja
• Michael Barley
• Daniel Borrajo
• Jordan Douglas
• Santiago Franco
• Patricia Riddle

Two key aspects of problem solving are representation and search heuristics. Both theoretical and experimental studies have shown that there is no one best problem representation nor one best search heuristic. Therefore, some recent methods, e. g. , portfolios, learn a good combination of problem solvers to be used in a given domain or set of domains. There are even dynamic portfolios that select a particular combination of problem solvers specific to a problem. These approaches: (1) need to perform a learning step; (2) do not usually focus on changing the representation of the input domain/problem; and (3) frequently do not adapt the portfolio to the specific problem. This paper describes a meta-reasoning system that searches through the space of combinations of representations and heuristics to find one suitable for optimally solving the specific problem. We show that this approach can be better than selecting a combination to use for all problems within a domain and is competitive with state of the art optimal planners.

AIJ Journal 2018 Journal Article

Symbolic perimeter abstraction heuristics for cost-optimal planning

• Álvaro Torralba
• Carlos Linares López
• Daniel Borrajo

In the context of heuristic search within automated planning, abstraction heuristics map the problem into an abstract instance and use the optimal solution cost in the abstract state space as an estimate for the real solution cost. Their flexibility in choosing different abstract mappings makes abstractions a powerful tool to obtain domain-independent heuristics. Different types of abstraction heuristics exist depending on how the mapping is defined, like Pattern Databases (PDBs) or Merge-and-Shrink (M&S). In this paper, we consider two variants of PDBs, symbolic and perimeter PDBs, combining them to take advantage of their synergy. Symbolic PDBs use decision diagrams in order to efficiently traverse the abstract state space. Perimeter PDBs derive more informed estimates by first constructing a perimeter around the goal and then using it to initialize the abstract search. We generalize this idea by considering a hierarchy of abstractions. Our algorithm starts by constructing a symbolic perimeter around the goal and, whenever continuing the search becomes unfeasible, it switches to a more abstracted state space. By delaying the use of an abstraction, the algorithm derives heuristics as informed as possible. Moreover, we prove that M&S abstractions with a linear merge strategy can be efficiently represented as decision diagrams, enabling the use of symbolic search with M&S abstractions as well as with PDBs. Our experimental evaluation shows that symbolic perimeter abstractions are competitive with other state-of-the-art heuristics.

IJCAI Conference 2016 Conference Paper

Abstraction Heuristics for Symbolic Bidirectional Search

• aacute; lvaro Torralba
• Carlos Linares L
• oacute; pez
• Daniel Borrajo

Symbolic bidirectional uniform-cost search is a prominent technique for cost-optimal planning. Thus, the question whether it can be further improved by making use of heuristic functions raises naturally. However, the use of heuristics in bidirectional search does not always improve its performance. We propose a novel way to use abstraction heuristics in symbolic bidirectional search in which the search only resorts to heuristics when it becomes unfeasible. We adapt the definition of partial and perimeter abstractions to bidirectional search, where A* is used to traverse the abstract state spaces and/or generate the perimeter. The results show that abstraction heuristics can further improve symbolic bidirectional search in some domains. In fact, the resulting planner, SymBA*, was the winner of the optimal-track of the last IPC.

AIJ Journal 2015 Journal Article

Automatic construction of optimal static sequential portfolios for AI planning and beyond

• Sergio Núñez
• Daniel Borrajo
• Carlos Linares López

In recent years the notion of portfolio has been revived with the aim of improving the performance of modern solvers. For example, Fast Downward Stone Soup and SATzilla have shown an excellent performance at the International Planning and SAT Competitions respectively. However, a deeper understanding of the limits and possibilities of portfolios is still missing. Most approaches to the study of portfolios are purely empirical. Thus, we propose a theoretically-grounded method based on Mixed-Integer Programming named gop. It addresses, among others, three main issues: how to derive an upper bound on the solvers performance for a given set of problem solving tasks; how to analyze the utility of training instances when designing portfolios; and how to configure a high performance portfolio for a given training set which generalizes very well on unseen instances. Experimental results both with data from the International Planning Competitions 2008 and 2011 and the SAT Competition 2013 show that this approach significantly outperforms others under the same conditions. Indeed, MIPSat, the sequential SAT portfolio automatically configured with gop, won the silver medal in the Open track of the SAT Competition 2013. In addition, MIPlan, the planning system which is able to automatically generate a portfolio configuration for a specific planning domain using gop, won the learning track of the International Planning Competition 2014.

IJCAI Conference 2015 Conference Paper

Sorting Sequential Portfolios in Automated Planning

• Sergio N
• uacute;
• ntilde; ez
• Daniel Borrajo
• Carlos Linares L
• oacute; pez

Recent work in portfolios of problem solvers has shown their ability to outperform single-algorithm approaches in some tasks (e. g. SAT or Automated Planning). However, not much work has been devoted to a better understanding of the relationship between the order of the component solvers and the performance of the resulting portfolio over time. We propose to sort the component solvers in a sequential portfolio, such that the resulting ordered portfolio maximizes the probability of providing the largest performance at any point in time. We empirically show that our greedy approach efficiently obtains near-optimal performance over time. Also, it generalizes much better than an optimal approach which has been observed to suffer from overfitting.

ICAPS Conference 2014 Conference Paper

Analyzing the Impact of Partial States on Duplicate Detection and Collision of Frontiers

• Vidal Alcázar
• Susana Fernández
• Daniel Borrajo

Partial states are states in which the truth value of one or more propositions is unknown. Such states are usually generated in regression and represent not a single state but rather a set of states. Because of this, a new partial state can be a subset of another existent partial state, phenomenon known as subsumption of states. Subsumed states can be pruned as if they were a duplicate. However, regular duplicate detection methods cannot detect such cases. Furthermore, subsumption of states also occurs when forward and backward search algorithms are integrated into a bidirectional planner. In these cases, the forward frontier contains only complete states and the backward frontier will often contain partial states. In this work, we analyze the impact that subsumption of states has on search and propose methods for duplicate detection and detection of collision of frontiers.

AAMAS Conference 2013 Conference Paper

Multi-Agent Planning by Plan Reuse

• Daniel Borrajo

Generating plans for a single agent has been shown to be a difficult task. If we generalize to a multi-agent setting, the problem becomes exponentially harder in general. The centralized approach where a plan is jointly generated for all agents is only possible in some applications when agents do not have private goals, actions or states. We describe in this paper an alternative approach, mapr (Multi-Agent Planning by plan Reuse), that considers both the agents private and public information. We have been inspired by iterative Multi-Agent Planning (MAP) techniques as the one presented in [3]. mapr first assigns a subset of public goals to each agent, while each agent might have a set of private goals also. Then, mapr calls the first agent to provide a solution (plan) that takes into account its private and public goals. mapr iteratively calls each agent with the solutions provided by previous agents. Each agent receives its own goals plus the goals of the previous agents. Thus, each agent solves its problem, but taking into account the previous agents solutions. Since previous solutions might consider private data, all private information from an agent is obfuscated for the next ones. Since each agent receives the plan from the previous agent that implicitly considers the solutions to all previous agents, instead of starting the search from scratch, it can also reuse the previous whole plan or only a subset of the actions. Experiments show that mapr outperforms in several orders of magnitude state-of-the-art techniques in the tested domains.

KER Journal 2013 Journal Article

On the automatic compilation of e-learning models to planning

• Antonio Garrido
• Susana Fernández
• Lluvia Morales
• Eva Onaindía
• Daniel Borrajo
• Luis Castillo

Abstract This paper presents a general approach to automatically compile e-learning models to planning, allowing us to easily generate plans, in the form of learning designs, by using existing domain-independent planners. The idea is to compile, first, a course defined in a standard e-learning language into a planning domain, and, second, a file containing students learning information into a planning problem. We provide a common compilation and extend it to three particular approaches that cover a full spectrum of planning paradigms, which increases the possibilities of using current planners: (i) hierarchical, (ii) including PDDL (Planning Domain Definition Language) actions with conditional effects and (iii) including PDDL durative actions. The learning designs are automatically generated from the plans and can be uploaded, and subsequently executed, by learning management platforms. We also provide an extensive analysis of the e-learning metadata specification required for planning, and the pros and cons on the knowledge engineering procedures used in each of the three compilations. Finally, we include some qualitative and quantitative experimentation of the compilations in several domain-independent planners to measure its scalability and applicability.

IJCAI Conference 2013 Conference Paper

Revisiting Regression in Planning

• Vidal Alcázar
• Daniel Borrajo
• Susana Fernández
• Raquel Fuentetaja

Heuristic search with reachability-based heuristics is arguably the most successful paradigm in Automated Planning to date. In its earlier stages of development, heuristic search was proposed as both forward and backward search. Due to the disadvantages of backward search, in the last decade researchers focused mainly on forward search, and backward search was abandoned for the most part as a valid alternative. In the last years, important advancements regarding both the theoretical understanding and the performance of heuristic search have been achieved, applied mainly to forward search planners. In this work we revisit regression in planning with reachabilitybased heuristics, trying to extrapolate to backward search current lines of research that were not as well understood as they are now.

IJCAI Conference 2013 Conference Paper

Symbolic Merge-and-Shrink for Cost-Optimal Planning

• Álvaro Torralba
• Carlos Linares López
• Daniel Borrajo

Symbolic PDBs and Merge-and-Shrink (M&S) are two approaches to derive admissible heuristics for optimal planning. We present a combination of these techniques, Symbolic Merge-and-Shrink (SM&S), which uses M&S abstractions as a relaxation criterion for a symbolic backward search. Empirical evaluation shows that SM&S has the strengths of both techniques deriving heuristics at least as good as the best of them for most domains.

KER Journal 2013 Journal Article

Using automated planning for improving data mining processes

• Susana Fernández
• Tomás de la Rosa
• Fernando Fernández
• Rubén Suárez
• Javier Ortiz
• Daniel Borrajo
• David Manzano

Abstract This paper presents a distributed architecture for automating data mining (DM) processes using standard languages. DM is a difficult task that relies on an exploratory and analytic process of processing large quantities of data in order to discover meaningful patterns. The increasing heterogeneity and complexity of available data requires some expert knowledge on how to combine the multiple and alternative DM tasks to process the data. Here, we describe DM tasks in terms of Automated Planning, which allows us to automate the DM knowledge flow construction. The work is based on the use of standards that have been defined in both DM and automated-planning communities. Thus, we use PMML (Predictive Model Markup Language) to describe DM tasks. From the PMML, a problem description in PDDL (Planning Domain Definition Language) can be generated, so any current planning system can be used to generate a plan. This plan is, again, translated to a DM workflow description, Knowledge Flow for Machine Learning format (Knowledge Flow file for the WEKA (Waikato Environment for Knowledge Analysis) tool), so the plan or DM workflow can be executed in WEKA.

KER Journal 2012 Journal Article

A review of machine learning for automated planning

• Sergio Jiménez
• Tomás de la Rosa
• Susana Fernández
• Fernando Fernández
• Daniel Borrajo

Abstract Recent discoveries in automated planning are broadening the scope of planners, from toy problems to real applications. However, applying automated planners to real-world problems is far from simple. On the one hand, the definition of accurate action models for planning is still a bottleneck. On the other hand, off-the-shelf planners fail to scale-up and to provide good solutions in many domains. In these problematic domains, planners can exploit domain-specific control knowledge to improve their performance in terms of both speed and quality of the solutions. However, manual definition of control knowledge is quite difficult. This paper reviews recent techniques in machine learning for the automatic definition of planning knowledge. It has been organized according to the target of the learning process: automatic definition of planning action models and automatic definition of planning control knowledge. In addition, the paper reviews the advances in the related field of reinforcement learning.

SoCS Conference 2012 Conference Paper

Performance Analysis of Planning Portfolios

• Sergio Núñez
• Daniel Borrajo
• Carlos Linares López

In recent years the concept of sequential portfolio has become an important topic to improve the performance of modern problem solvers, such as SAT engines or planners. The PbP planner and more recently Fast Downward Stone Soup are successful approaches in Automated Planning that follow this trend. However, neither a theoretical analysis nor formal definitions about sequential portfolios have been described. In this paper, we focus on studying how to evaluate the performance of planners defining a baseline for a set of problems. We present a general method based on Mixed-Integer Programming to define the baseline for a training data set. In addition to prior work, we also introduce a short empirical analysis of the utility of training problems to configure sequential portfolios.

SoCS Conference 2011 Conference Paper

Adapting a Rapidly-Exploring Random Tree for Automated Planning

• Vidal Alcázar
• Manuela Veloso
• Daniel Borrajo

Rapidly-exploring random trees (RRTs) are data structures and search algorithms designed to be used in continuous path planning problems. They are one of the most successful state-of-the-art techniques as they offer a great degree of flexibility and reliability. However, their use in other search domains has not been thoroughly analyzed. In this work we propose the use of RRTs as a search algorithm for automated planning. We analyze the advantages that this approach has over previously used search algorithms and the challenges of adapting RRTs for implicit and discrete search spaces.

ICAPS Conference 2011 Conference Paper

Planning Multi-Modal Transportation Problems

• José E. Flórez
• Álvaro Torralba
• Javier García 0001
• Carlos Linares López
• Ángel García Olaya
• Daniel Borrajo

Multi-modal transportation is a logistics problem in which a set of goods have to be transported to different places, with the combination of at least two modes of transport, without a change of container for the goods. The goal of this paper is to describe TIMIPLAN, a system that solves multi-modal transportation problems in the context of a project for a big company. In this paper, we combine Linear Programming (LP) with automated planning techniques in order to obtain good quality solutions. The direct use of classical LP techniques is difficult in this domain, because of the non-linearity of the optimization function and constraints; and planning algorithms cannot deal with the entire problem due to the large number of resources involved. We propose a new hybrid algorithm, combining LP and planning to tackle the multi-modal transportation problem, exploiting the benefits of both kinds of techniques. The system also integrates an execution component that monitors the execution, keeping track of failures and replans if necessary, maintaining most of the plan in execution. We also present some experimental results that show the performance of the system.

SoCS Conference 2010 Conference Paper

Adding Diversity to Classical Heuristic Planning

• Carlos Linares López
• Daniel Borrajo

In this paper we propose a new algorithm for solving general two-player turn-taking games that performs symbolic search utilizing binary decision diagrams (BDDs). It consists of two stages: First, it determines all breadth-first search (BFS) layers using forward search and omitting duplicate detection, next, the solving process operates in backward direction only within these BFS layers thereby partitioning all BDDs according to the layers the states reside in. We provide experimental results for selected games and compare to a previous approach. This comparison shows that in most cases the new algorithm outperforms the existing one in terms of runtime and used memory so that it can solve games that could not be solved before with a general approach.

ICAPS Conference 2010 Conference Paper

Using Backwards Generated Goals for Heuristic Planning

• Vidal Alcázar
• Daniel Borrajo
• Carlos Linares López

Forward State Planning with Reachability Heuristics is arguably the most successful approach to Automated Planning up to date. In addition to an estimation of the distance to the goal, relaxed plans obtained with such heuristics provide the search with useful information such as helpful actions and look-ahead states. However, this information is extracted only from the beginning of the relaxed plan. In this paper, we propose using information extracted from the last actions in the relaxed plan to generate intermediate goals backwards. This allows us to use information from previous computations of the heuristic and reduce the depth of the search tree.

ICAPS Conference 2008 Conference Paper

Learning Relational Decision Trees for Guiding Heuristic Planning

• Tomás de la Rosa
• Sergio Jiménez Celorrio
• Daniel Borrajo

The current evaluation functions for heuristic planning are expensive to compute. In numerous domains these functions give good guidance on the solution, so it worths the computation effort. On the contrary, where this is not true, heuristics planners compute loads of useless node evaluations that make them scale-up poorly. In this paper we present a novel approach for boosting the scalability of heuristic planners based on automatically learning domain-specific search control knowledge in the form of relational decision trees. Particularly, we define the learning of planning search control as a standard classification process. Then, we use an off-the-shelf relational classifier to build domain-specific relational decision trees that capture the preferred action in the different planning contexts of a planning domain. These contexts are defined by the set of helpful actions extracted from the relaxed planning graph of a given state, the goals remaining to be achieved, and the static predicates of the planning task. Additionally, we show two methods for guiding the search of a heuristic planner with relational decision trees. The first one consists of using the resulting decision trees as an action policy. The second one consists of ordering the node evaluation of the Enforced Hill Climbing algorithm with the learned decision trees. Experiments over a variety of domains from the IPC test-benchmarks reveal that in both cases the use of the learned decision trees increase the number of problems solved together with a reduction of the time spent.

IJCAI Conference 2007 Conference Paper

• Susana Fern
• aacute; ndez
• Ricardo Aler
• Daniel Borrajo

As any other problem solving task that employs search, AI Planning needs heuristics to efficiently guide the problem-space exploration. Machine learning (ML) provides several techniques for automatically acquiring those heuristics. Usually, a planner solves a problem, and a ML technique generates knowledge from the search episode in terms of complete plans (macro-operators or cases), or heuristics (also named control knowledge in planning). In this paper, we present a novel way of generating planning heuristics: we learn heuristics in one planner and transfer them to another planner. This approach is based on the fact that different planners employ different search bias. We want to extract knowledge from the search performed by one planner and use the learned knowledge on another planner that uses a different search bias. The goal is to improve the efficiency of the second planner by capturing regularities of the domain that it would not capture by itself due to its bias. We employ a deductive learning method (\ebl) that is able to automatically acquire control knowledge by generating bounded explanations of the problem-solving episodes in a Graphplan-based planner. Then, we transform the learned knowledge so that it can be used by a bidirectional planner.

KER Journal 2007 Journal Article

PLTOOL: A knowledge engineering tool for planning and learning

• Susana Fernández
• Daniel Borrajo
• Raquel Fuentetaja
• Juan D. Arias
• Manuela Veloso

Absract Artificial intelligence (AI) planning solves the problem of generating a correct and efficient ordered set of instantiated activities, from a knowledge base of generic actions, which when executed will transform some initial state into some desirable end-state. There is a long tradition of work in AI for developing planners that make use of heuristics that are shown to improve their performance in many real world and artificial domains. The developers of planners have chosen between two extremes when defining those heuristics. The domain-independent planners use domain-independent heuristics, which exploit information only from the ‘syntactic’ structure of the problem space and of the search tree. Therefore, they do not need any ‘semantic’ information from a given domain in order to guide the search. From a knowledge engineering (KE) perspective, the planners that use this type of heuristics have the advantage that the users of this technology need only focus on defining the domain theory and not on defining how to make the planner efficient (how to obtain ‘good’ solutions with the minimal computational resources). However, the domain-dependent planners require users to manually represent knowledge not only about the domain theory, but also about how to make the planner efficient. This approach has the advantage of using either better domain-theory formulations or using domain knowledge for defining the heuristics, thus potentially making them more efficient. However, the efficiency of these domain-dependent planners strongly relies on the KE and planning expertise of the user. When the user is an expert on these two types of knowledge, domain-dependent planners clearly outperform domain-independent planners in terms of number of solved problems and quality of solutions. Machine-learning (ML) techniques applied to solve the planning problems have focused on providing middle-ground solutions as compared to the aforementioned two extremes. Here, the user first defines a domain theory, and then executes the ML techniques that automatically modify or generate new knowledge with respect to both the domain theory and the heuristics. In this paper, we present our work on building a tool, PLTOOL (planning and learning tool), to help users interact with a set of ML techniques and planners. The goal is to provide a KE framework for mixed-initiative generation of efficient and good planning knowledge.

ECAI Conference 2004 Conference Paper

IPSS: A Hybrid Reasoner for Planning and Scheduling

• María D. R. -Moreno
• Angelo Oddi
• Daniel Borrajo
• Amedeo Cesta
• Daniel Meziat

ICAPS Conference 2002 Conference Paper

On Control Knowledge Acquisition by Exploiting Human-Computer Interaction

• Ricardo Aler
• Daniel Borrajo

In the last decade, there has been a strong and increasing interest on building fast planning systems. From it, we have seen an enormous improvement in relation to the solvability horizon of current planning techniques. Most of these techniques rely on the translation of the predicate logic description of domains into propositional representations of them. Then, a fast search procedure is applied for obtaining solutions to planning problems. While this is an important step towards solving the planning problem, we believe older planners that are based on predicate logic computation can still be competitive when they are combined with learning capabilities. This is so, because they can acquire and use more abstract representations of control knowledge (CK) which are easier to describe and maintain by humans and/or automatic systems than the ones based on propositional logic. In this paper, we present the results we have obtained with a relatively "old" planner, Prodigy4. 0, powered with CK that has been acquired using a mixed human-computer collaboration. We advocate for the initial generation of CK by a learning system, and its later refinement by a human. In fact, we can iterate this process until the desired result has been achieved. We show results in the logistics domain used at AIPS'00 that are at the same level when compared with other techniques in the Track on hand-tailored planning systems (Track2).

ECAI Conference 2002 Conference Paper

On Determinism Handling While Learning Reduced State Space Representations

• Fernando Fernández 0001
• Daniel Borrajo

AIJ Journal 2002 Journal Article

Using genetic programming to learn and improve control knowledge

• Ricardo Aler
• Daniel Borrajo
• Pedro Isasi

The purpose of this article is to present a multi-strategy approach to learn heuristics for planning. This multi-strategy system, called Hamlet-EvoCK, combines a learning algorithm specialized in planning (Hamlet) and a genetic programming (GP) based system (EvoCK: Evolution of Control Knowledge). Both systems are able to learn heuristics for planning on their own, but both of them have weaknesses. Based on previous experience and some experiments performed in this article, it is hypothesized that Hamlet handicaps are due to its example-driven operators and not having a way to evaluate the usefulness of its control knowledge. It is also hypothesized that even if Hamlet control knowledge is sometimes incorrect, it might be easily correctable. For this purpose, a GP-based stage is added, because of its complementary biases: GP genetic operators are not example-driven and it can use a fitness function to evaluate control knowledge. Hamlet and EvoCK are combined by seeding EvoCK initial population with Hamlet control knowledge. It is also useful for EvoCK to start from a knowledge-rich population instead of a random one. By adding the GP stage to Hamlet, the number of solved problems increases from 58% to 85% in the blocks world and from 50% to 87% in the logistics domain (0% to 38% and 0% to 42% for the hardest instances of problems considered).

ICML Conference 2000 Conference Paper

Knowledge Representation Issues in Control Knowledge Learning

• Ricardo Aler
• Daniel Borrajo
• Pedro Isasi

ICML Conference 1998 Conference Paper

Genetic Programming and Deductive-Inductive Learning: A Multi-Strategy Approach

• Ricardo Aler
• Daniel Borrajo
• Pedro Isasi

ICAPS Conference 1998 Conference Paper

Genetic Programming of Control Knowledge for Planning

• Ricardo Aler
• Daniel Borrajo
• Pedro Isasi

It is well knownthat planning for complex domainsand non-trivial problemsis a difficult task for domain independent planners. Adding domain knowledgeto the planner is a simple approach to improveits efficiency for a given domain. In this paper we present EvoCK, a system based on Genetic Programming, which produces control knowledge for a nonlinear domain independent planner (PRODIGY4. 0). EvoCKhas been tested in two domains (the blocksworld and logistics), and very good experimental results have been obtained both in terms of the numberof problems solved and of the quality of the control-rules produced.

AIJ Journal 1997 Journal Article

A computational approach to George Boole's discovery of mathematical logic

• Luis de Ledesma
• Aurora Pérez
• Daniel Borrajo
• Luis M. Laita

This paper reports a computational model of Boole's discovery of Logic as a part of Mathematics. George Boole (1815–1864) found that the symbols of Logic behaved as algebraic symbols, and he then rebuilt the whole contemporary theory of Logic by the use of methods such as the solution of algebraic equations. Study of the different historical factors that influenced this achievement has served as background for our two main contributions: a computational representation of Boole's Logic before it was mathematized; and a production system, BOOLE2, that rediscovers Logic as a science that behaves exactly as a branch of Mathematics, and that thus validates to some extent the historical explanation. The system's discovery methods are found to be general enough to handle three other cases: two versions of a Geometry due to a contemporary of Boole, and a small subset of the Differential Calculus.