Author name cluster

Nir Lipovetzky

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.

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

AAAI Conference 2025 Conference Paper

Planning in the Dark: LLM-Symbolic Planning Pipeline Without Experts

Sukai Huang
Nir Lipovetzky
Trevor Cohn

Large Language Models (LLMs) have shown promise in solving natural language-described planning tasks, but their direct use often leads to inconsistent reasoning and hallucination. While hybrid LLM-symbolic planning pipelines have emerged as a more robust alternative, they typically require extensive expert intervention to refine and validate generated action schemas. It not only limits scalability but also introduces a potential for biased interpretation, as a single expert's interpretation of ambiguous natural language descriptions might not align with the user's actual intent. To address this, we propose a novel approach that constructs an action schema library to generate multiple candidates, accounting for the diverse possible interpretations of natural language descriptions. We further introduce a semantic validation and ranking module that automatically filter and rank these candidates without expert-in-the-loop. The experiments showed our pipeline maintains superiority in planning over the direct LLM planning approach. These findings demonstrate the feasibility of a fully automated end-to-end LLM-symbolic planner that requires no expert intervention, opening up the possibility for a broader audience to engage with AI planning with less prerequisite of domain expertise.

PDF Details DOI

AAAI Conference 2025 Conference Paper

State-Based Disassembly Planning

Chao Lei
Nir Lipovetzky
Krista A. Ehinger

It has been shown recently that physics-based simulation significantly enhances the disassembly capabilities of real-world assemblies with diverse 3D shapes and stringent motion constraints. However, the efficiency suffers when tackling intricate disassembly tasks that require numerous simulations and increased simulation time. In this work, we propose a State-Based Disassembly Planning (SBDP) approach, prioritizing physics-based simulation with translational motion over rotational motion to facilitate autonomy, reducing dependency on human input, while storing intermediate motion states to improve search scalability. We introduce two novel evaluation functions derived from new Directional Blocking Graphs (DBGs) enriched with state information to scale up the search. Our experiments show that SBDP with new evaluation functions and DBGs constraints outperforms the state-of-the-art in disassembly planning in terms of success rate and computational efficiency over benchmark datasets consisting of thousands of physically valid industrial assemblies.

PDF Details DOI

PRL Workshop 2025 Workshop Paper

The Dark Side of Rich Rewards: Understanding and Mitigating Noise in VLM Rewards

Sukai Huang
Shu-Wei Liu
Nir Lipovetzky
Trevor Cohn

While Vision-Language Models (VLMs) are increasingly used to generate reward signals for training embodied agents to follow instructions, our research reveals that agents guided by VLM rewards often underperform compared to those employing only intrinsic (exploration-driven) rewards, contradicting expectations set by recent work. We hypothesize that false positive rewards – instances where unintended trajectories are incorrectly rewarded – are more detrimental than false negatives. We confirmed this hypothesis, revealing that the widely used cosine similarity metric is prone to false positive estimates. To address this, we introduce B I MI (Binary Mutual Information), a novel reward function designed to mitigate noise. B I MI significantly enhances learning efficiency across diverse and challenging embodied navigation environments. Our findings offer a nuanced insight of how different types of reward noise impact agent learning and highlight the importance of addressing multimodal reward signal noise when training embodied agents.

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.

IROS Conference 2024 Conference Paper

Beyond Success: Quantifying Demonstration Quality in Learning from Demonstration

Muhammad Bilal
Nir Lipovetzky
Denny Oetomo
Wafa Johal

Learning from Demonstration (LfD) empowers novice users to teach robots daily life tasks without writing sophisticated code, thereby promoting the democratization of robotics. However, novice users often provide sub-optimal demonstrations, which can potentially impact the robot’s ability to efficiently learn and execute the tasks. Prior research has assessed the quality of demonstrations by evaluating the robot’s task performance; however, the approach remains insufficient to qualify individual demonstrations, leaving the reason for classifying demonstrations as high- or low-quality unknown. Therefore, this simulation-based study aims to quantify the quality of individual demonstration at each step by incorporating motion-related quality features such as manipulability and joint-space jerk. To assess the efficacy of these features, we initially evaluated the given demonstrations—taking into account each quality feature—to rank them from high- to low-quality. Subsequently, we investigated the impact of demonstration’s quality on task performance and the quality of task execution. In this pursuit, we trained a series of LfD models for distinct manipulation tasks: cube lifting and pick-and-place of soda can. Our results illustrate a strong correlation between ranked demonstrations and the quality of task execution. Interestingly, we observed that the quality features have a significant impact on task performance, particularly when the provided demonstrations exhibit diversity in terms of quality. Overall, this analysis enables quantifying the quality of individual demonstrations based on motion-related quality features, thus improving learning from demonstration.

ECAI Conference 2024 Conference Paper

Count-Based Novelty Exploration in Classical Planning

Giacomo Rosa
Nir Lipovetzky

Count-based exploration methods are widely employed to improve the exploratory behavior of learning agents over sequential decision problems. Meanwhile, Novelty search has achieved success in Classical Planning through recording of the first, but not successive, occurrences of tuples. In order to structure the exploration, however, the number of tuples considered needs to grow exponentially as the search progresses. We propose a new novelty technique, classical count-based novelty, which aims to explore the state space with a constant number of tuples, by leveraging the frequency of each tuple’s appearance in a search tree. We then justify the mechanisms through which lower tuple counts lead the search towards novel tuples. We also introduce algorithmic contributions in the form of a trimmed open list that maintains a constant size by pruning nodes with bad novelty values. These techniques are shown to complement existing novelty heuristics when integrated in a classical solver, achieving competitive results in challenging benchmarks from recent International Planning Competitions. Moreover, adapting our solver as the frontend planner in dual configurations that utilize both memory and time thresholds demonstrates a significant increase in instance coverage, surpassing current state-of-the-art solvers.

AAAI Conference 2024 Conference Paper

Generalized Planning for the Abstraction and Reasoning Corpus

Chao Lei
Nir Lipovetzky
Krista A. Ehinger

The Abstraction and Reasoning Corpus (ARC) is a general artificial intelligence benchmark that poses difficulties for pure machine learning methods due to its requirement for fluid intelligence with a focus on reasoning and abstraction. In this work, we introduce an ARC solver, Generalized Planning for Abstract Reasoning (GPAR). It casts an ARC problem as a generalized planning (GP) problem, where a solution is formalized as a planning program with pointers. We express each ARC problem using the standard Planning Domain Definition Language (PDDL) coupled with external functions representing object-centric abstractions. We show how to scale up GP solvers via domain knowledge specific to ARC in the form of restrictions over the actions model, predicates, arguments and valid structure of planning programs. Our experiments demonstrate that GPAR outperforms the state-of-the-art solvers on the object-centric tasks of the ARC, showing the effectiveness of GP and the expressiveness of PDDL to model ARC problems. The challenges provided by the ARC benchmark motivate research to advance existing GP solvers and understand new relations with other planning computational models. Code is available at github.com/you68681/GPAR.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Human Goal Recognition as Bayesian Inference: Investigating the Impact of Actions, Timing, and Goal Solvability

Chenyuan Zhang
Charles Kemp
Nir Lipovetzky

Goal recognition is a fundamental cognitive process that enables individuals to infer intentions based on available cues. Current goal recognition algorithms often take only observed actions as input, but here we use a Bayesian framework to explore the role of actions, timing, and goal solvability in goal recognition. We analyze human responses to goal-recognition problems in the Sokoban domain, and find that actions are assigned most importance, but that timing and solvability also influence goal recognition in some cases, especially when actions are uninformative. We leverage these findings to develop a goal recognition model that matches human inferences more closely than do existing algorithms. Our work provides new insight into human goal recognition and takes a step towards more human-like AI models.

HAXP Workshop 2023 Workshop Paper

Comparing AI planning algorithms with humans on the Tower of London task

Chenyuan Zhang
Nir Lipovetzky
Charles Kemp

Understanding problem solving or planning has been a shared challenge for both AI and cognitive science since the birth of both fields. We explore the extent to which modern planners from the field of AI can account for human performance on the Tower of London (TOL) task, a close relative of the Tower of Hanoi problem that has been extensively studied by psychologists. We characterize the task using the Planning Domain Definition Language (PDDL) and evaluate an adaptive online planner and a family of well-known planners, including online planners, optimal planners and satisficing planners. Each planner is evaluated based on its ability to predict the actions and planning times of participants in a new behavioral experiment. Our results suggest that participants use a range of strategies but that an adaptive lookahead planner provides the best overall account of both human actions and human planning times. This finding is consistent with the view that humans differ from standard AI planners by integrating a mechanism for evidence accumulation.

ECAI Conference 2023 Conference Paper

Diverse, Top-k, and Top-Quality Planning Over Simulators

Lyndon Benke
Tim Miller 0001
Michael Papasimeon
Nir Lipovetzky

Diverse, top-k, and top-quality planning are concerned with the generation of sets of solutions to sequential decision problems. Previously this area has been the domain of classical planners that require a symbolic model of the problem instance. This paper proposes a novel alternative approach that uses Monte Carlo Tree Search (MCTS), enabling application to problems for which only a black-box simulation model is available. We present a procedure for extracting bounded sets of plans from pre-generated search trees in best-first order, and a metric for evaluating the relative quality of paths through a search tree. We demonstrate this approach on a path-planning problem with hidden information, and suggest adaptations to the MCTS algorithm to increase the diversity of generated plans. Our results show that our method can generate diverse and high-quality plan sets in domains where classical planners are not applicable.

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.

ICAPS Conference 2023 Conference Paper

Goal Recognition with Timing Information

Chenyuan Zhang
Charles Kemp
Nir Lipovetzky

Goal recognition has been extensively studied by AI researchers, but most algorithms take only observed actions as input. Here we argue that the time taken to carry out these actions provides an additional signal that supports goal recognition. We present a behavioral experiment confirming that people use timing information in this way, and develop and evaluate a goal recognition algorithm that is sensitive to both actions and timing information. Our results suggest that existing goal recognition algorithms can be improved by incorporating a model of planning time on both synthetic data and human data, and that these improvements can be substantial in scenarios in which relatively few actions have been observed.

SoCS Conference 2023 Conference Paper

Novelty and Lifted Helpful Actions in Generalized Planning

Chao Lei
Nir Lipovetzky
Krista A. Ehinger

It has been shown recently that successful techniques in classical planning, such as goal-oriented heuristics and landmarks, can improve the ability to compute planning programs for generalized planning (GP) problems. In this work, we introduce the notion of action novelty rank, which computes novelty with respect to a planning program, and propose novelty-based generalized planning solvers, which prune a newly generated planning program if its most frequent action repetition is greater than a given bound v, implemented by novelty-based best-first search BFS(v) and its progressive variant PGP(v). Besides, we introduce lifted helpful actions in GP derived from action schemes, and propose new evaluation functions and structural program restrictions to scale up the search. Our experiments show that the new algorithms BFS(v) and PGP(v) outperform the state-of-the-art in GP over the standard generalized planning benchmarks. Practical findings on the above-mentioned methods in generalized planning are briefly discussed.

ICAPS Conference 2023 Conference Paper

Planning with Multi-Agent Belief Using Justified Perspectives

Guang Hu 0003
Tim Miller 0001
Nir Lipovetzky

Epistemic planning plays an important role in multi-agent and human-agent interaction domains. Most existing works solve multi-agent epistemic planning problems by either pre-compiling them into classical planning problems; or, using explicit actions and their effects to encode Kripke-based semantics. A recent approach called Planning with Perspectives (PWP) delegates epistemic reasoning in planning to external functions using F-STRIPS, keeping the search within the planning algorithm and lazily evaluating epistemic formulae. Although PWP is expressive and efficient, it models S5 epistemic logic and does not support belief, including false belief. In this paper, we extend the PWP model to handle multi-agent belief by following the intuition that agents believe something they have seen until they see otherwise. We call this justified perspectives. We formalise this notion of multi-agent belief based on the definition of knowledge in PWP. Using experiments on existing epistemic and doxastic planning benchmarks, we show that our belief planner can solve benchmarks more efficiently than the state-of-the-art baseline, and can model some problems that are infeasible to model using propositional-based approaches.

AIJ Journal 2023 Journal Article

Width-based search for multi agent privacy-preserving planning

Alfonso E. Gerevini
Nir Lipovetzky
Francesco Percassi
Alessandro Saetti
Ivan Serina

In multi-agent planning, preserving the agents' privacy has become an increasingly popular research topic. For preserving the agents' privacy, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, this can severely restrict the accuracy of the heuristic functions used while searching for solutions. It has been recently shown that, for centralized planning, blind search algorithms such as width-based search can solve instances of many existing domains in low polynomial time when they feature atomic goals. Moreover, the performance of goal-oriented search can be improved by combining it with width-based search. In this paper, we investigate the usage of width-based search in the context of (decentralised) collaborative multi-agent privacy-preserving planning, addressing the challenges related to the agents' privacy and performance. In particular, we show that width-based search is a very effective approach over several benchmark domains, even when the search is driven by heuristics that roughly estimate the distance from goal states, computed without using the private information of other involved agents. Moreover, we show that the use of width-based techniques can significantly reduce the number of messages transmitted among the agents, better preserving their privacy and improving their performance. An experimental study presented in the paper analyses the effectiveness of our techniques, and compares them with the state-of-the-art of collaborative multi-agent planning.

SoCS Conference 2022 Conference Paper

On the Use of Width-Based Search for Multi Agent Privacy-Preserving Planning (Extended Abstract)

Alfonso Emilio Gerevini
Nir Lipovetzky
Francesco Percassi
Alessandro Saetti
Ivan Serina

The aim of decentralised multi-agent (DMA) planning is to coordinate a set of agents to jointly achieve a goal while preserving their privacy. Blind search algorithms, such as width-based search, have recently proved to be very effective in the context of centralised automated planning, especially when combined with goal-oriented techniques. In this paper, we discuss a recent line of research in which the usage of width-based search has been extensively studied in the context of DMA planning, addressing the challenges related to the agents

JAIR Journal 2022 Journal Article

Planning with Perspectives -- Decomposing Epistemic Planning using Functional STRIPS

Guang Hu
Tim Miller
Nir Lipovetzky

In this paper, we present a novel approach to epistemic planning called planning with perspectives (PWP) that is both more expressive and computationally more efficient than existing state-of-the-art epistemic planning tools. Epistemic planning — planning with knowledge and belief — is essential in many multi-agent and human-agent interaction domains. Most state-of-the-art epistemic planners solve epistemic planning problems by either compiling to propositional classical planning (for example, generating all possible knowledge atoms or compiling epistemic formulae to normal forms); or explicitly encoding Kripke-based semantics. However, these methods become computationally infeasible as problem sizes grow. In this paper, we decompose epistemic planning by delegating reasoning about epistemic formulae to an external solver. We do this by modelling the problem using Functional STRIPS, which is more expressive than standard STRIPS and supports the use of external, black-box functions within action models. Building on recent work that demonstrates the relationship between what an agent ‘sees’ and what it knows, we define the perspective of each agent using an external function, and build a solver for epistemic logic around this. Modellers can customise the perspective function of agents, allowing new epistemic logics to be defined without changing the planner. We ran evaluations on well-known epistemic planning benchmarks to compare an existing state-of-the-art planner, and on new scenarios that demonstrate the expressiveness of the PWP approach. The results show that our PWP planner scales significantly better than the state-of-the-art planner that we compared against, and can express problems more succinctly.

PDF Details DOI

SoCS Conference 2022 Conference Paper

Sampling from Pre-Images to Learn Heuristic Functions for Classical Planning (Extended Abstract)

Stefan O'Toole
Miquel Ramírez
Nir Lipovetzky
Adrian R. Pearce

We introduce a new algorithm, Regression based Supervised Learning (RSL), for learning per instance Neural Network (NN) defined heuristic functions for classical planning problems. RSL uses regression to select relevant sets of states at a range of different distances from the goal. RSL then formulates a Supervised Learning problem to obtain the parameters that define the NN heuristic, using the selected states labeled with exact or estimated distances to goal states. Our experimental study shows that RSL outperforms, in terms of coverage, previous classical planning NN heuristics functions while requiring a fraction of the training time.

ICAPS Conference 2021 Conference Paper

Approximate Novelty Search

Anubhav Singh
Nir Lipovetzky
Miquel Ramírez
Javier Segovia-Aguas

Width-based search algorithms seek plans by prioritizing states according to a suitably defined measure of novelty, that maps states into a set of novelty categories. Space and time complexity to evaluate state novelty is known to be exponential on the cardinality of the set. We present novel methods to obtain polynomial approximations of novelty and width-based search. First, we approximate novelty computation via random sampling and Bloom filters, reducing the runtime and memory footprint. Second, we approximate the best-first search using an adaptive policy that decides whether to forgo the expansion of nodes in the open list. These two techniques are integrated into existing width-based algorithms, resulting in new planners that perform significantly better than other state-of-the-art planners over benchmarks from the International Planning Competitions.

IJCAI Conference 2021 Conference Paper

Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning

Nir Lipovetzky

Width-based algorithms search for solutions through a general definition of state novelty. These algorithms have been shown to result in state-of-the-art performance in classical planning, and have been successfully applied to model-based and model-free settings where the dynamics of the problem are given through simulation engines. Width-based algorithms performance is understood theoretically through the notion of planning width, providing polynomial guarantees on their runtime and memory consumption. To facilitate synergies across research communities, this paper summarizes the area of width-based planning, and surveys current and future research directions.

PDF Details DOI

ICAPS Conference 2021 Conference Paper

Width-Based Backward Search

Chao Lei
Nir Lipovetzky

It has been shown recently that duality mapping is a viable strategy to turn progression (forward search) into regression (backward search), but the experimental results suggest that the dual versions of standard IPC benchmarks are quite difficult to solve for heuristic search planners. We aim to study the performance of width-based planners over regression. Our experiments show that width-based search can solve dual problems efficiently when the goal state is restricted to single fluent, but it becomes challenging when the goal state contains conjunctive fluents. We then show that the backward version of best-first width-search (BFWS) with the evaluation function f5, BFWS(f5), and its polynomial variant, k-BFWS(f5), are not competitive with their forward versions, but can be orthogonal over the IPC benchmarks. Hence, we propose a front-to-end bidirectional search k-BDWS-e and its front-to-front variant by integrating forward and backward k-BFWS(f5) with the additional intersection check between expanded states whose novelty is 1 in the opposite Close list. Practical findings on the challenges of regression in classical planning are briefly discussed.

NeurIPS Conference 2021 Conference Paper

Width-based Lookaheads with Learnt Base Policies and Heuristics Over the Atari-2600 Benchmark

Stefan O'Toole
Nir Lipovetzky
Miquel Ramirez
Adrian Pearce

We propose new width-based planning and learning algorithms inspired from a careful analysis of the design decisions made by previous width-based planners. The algorithms are applied over the Atari-2600 games and our best performing algorithm, Novelty guided Critical Path Learning (N-CPL), outperforms the previously introduced width-based planning and learning algorithms $\pi$-IW(1), $\pi$-IW(1)+ and $\pi$-HIW(n, 1). Furthermore, we present a taxonomy of the Atari-2600 games according to some of their defining characteristics. This analysis of the games provides further insight into the behaviour and performance of the algorithms introduced. Namely, for games with large branching factors, and games with sparse meaningful rewards, N-CPL outperforms $\pi$-IW, $\pi$-IW(1)+ and $\pi$-HIW(n, 1).

IJCAI Conference 2020 Conference Paper

Boundary Extension Features for Width-Based Planning with Simulators on Continuous-State Domains

Florent Teichteil-Königsbuch
Miquel Ramirez
Nir Lipovetzky

Width-based planning algorithms have been demonstrated to be competitive with state-of-the-art heuristic search and SAT-based approaches, without requiring access to a model of action effects and preconditions, just access to a black-box simulator. Width-based planners search is guided by a measure of the novelty of states, that requires observations on simulator states to be given as a set of features. This paper proposes agnostic feature mapping mechanisms that define the features online, as exploration progresses and the domain of continuous state variables is revealed. We demonstrate the effectiveness of these features on the OpenAI gym "classical control" suite of benchmarks. We compare our online planners with state-of-the-art deep reinforcement learning algorithms, and show that width-based planners using our features can find policies of the same quality with significantly less computational resources.

PDF Details DOI

ICAPS Conference 2019 Conference Paper

Best-First Width Search for Multi Agent Privacy-Preserving Planning

Alfonso Emilio Gerevini
Nir Lipovetzky
Francesco Percassi
Alessandro Saetti
Ivan Serina

In multi-agent planning, preserving the agents’ privacy has become an increasingly popular research topic. For preserving the agents’ privacy, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, this can severely restrict the accuracy of the heuristic functions used while searching for solutions. It has been recently shown that, for centralized planning, the performance of goal oriented search can be improved by combining goal oriented search and width-based search. The combination of these techniques has been called best-first width search. In this paper, we investigate the usage of best-first width search in the context of (decentralised) multi-agent privacy-preserving planning, addressing the challenges related to the agents’ privacy and performance. In particular, we show that best-first width search is a very effective approach over several benchmark domains, even when the search is driven by heuristics that roughly estimate the distance from goal states, computed without using the private information of other agents. An experimental study analyses the effectiveness of our techniques and compares them with the state-of-the-art.

SoCS Conference 2019 Conference Paper

Novelty Messages Filtering for Multi Agent Privacy-Preserving Plannin

Alfonso Emilio Gerevini
Nir Lipovetzky
Nico Peli
Francesco Percassi
Alessandro Saetti
Ivan Serina

In multi-agent planning, agents jointly compute a plan that achieves mutual goals, keeping certain information private to the individual agents. Agents

AAMAS Conference 2018 Conference Paper

Action Selection for Transparent Planning

Aleck M. MacNally
Nir Lipovetzky
Miquel Ramirez
Adrian R. Pearce

We introduce a novel framework to formalize and solve transparent planning tasks by executing actions selected in a suitable and timely fashion. A transparent planning task is defined as a task where the objective of the agent is to communicate its true goal to observers, thereby making its intentions and its action selection transparent. We formally define and model these tasks as Goal Pomdps where the state space is the Cartesian product of the states of the world and a given set of hypothetical goals. Action effects are deterministic in the world states of the problem but probabilistic in the observer’s beliefs. Transition probabilities are obtained from making a call to a model–based plan recognition algorithm, which we refer to as an observer stereotype. We propose an action selection strategy via on– line planning that seeks actions to quickly convey the goal being pursued to an observer assumed to fit a given stereotype. In order to keep run–times feasible, we propose a novel model–based plan recognition algorithm that approximates well–known probabilistic plan recognition methods. The resulting on–line planner, after being evaluated over a diverse set of domains and three different observer stereotypes, is found to convey goal information faster than purely goal–directed planners.

AAMAS Conference 2018 Conference Paper

Integrated Hybrid Planning and Programmed Control for Real-Time UAV Maneuvering

Miquel Ramirez
Michael Papasimeon
Nir Lipovetzky
Lyndon Benke
Tim Miller
Adrian R. Pearce
Enrico Scala
Mohammad Zamani

The automatic generation of realistic behaviour such as tactical intercepts for Unmanned Aerial Vehicles (UAV) in air combat is a challenging problem. State-of-the-art solutions propose handś crafted algorithms and heuristics whose performance depends heavily on the initial conditions and aerodynamic properties of the UAVs involved. This paper shows how to employ domainśindependent planners, embedded into professional multiśagent simulations, to implement twoślevel Model Predictive Control (MPC) hybrid control systems for simulated UAVs. We compare the performance of controllers using planners with others based on behaviour trees that implement real world tactics. Our results indicate that hybrid planners derive novel and efective tactics from irst principles inherent to the dynamical constraints UAVs are subject to.

ICAPS Conference 2017 Conference Paper

A Polynomial Planning Algorithm that Beats LAMA and FF

Nir Lipovetzky
Hector Geffner

It has been shown recently that heuristic and width-based search can be combined to produce planning algorithms with a performance that goes beyond the state-of-the-art. Such algorithms are based on best-first width search (BFWS), a plain best-first search set with evaluations functions combined lexicographically to break ties, some of which express novelty based preferences. In BFWS(f5), for example, the evaluation function f5 weights nodes by a novelty measure, breaking ties by the number of non-achieved goals. BFWS(f5) is a best-first algorithm, and hence, it is complete but not polynomial, and its performance doesn’t match the state of the art. In this work we show, however, that incomplete versions of BFWS(f5) where nodes with novelty greater than k are pruned, are not only polynomial but have an empirical performance that is better than both BFWS(f5) and state-of-the-art planners. This is shown by considering all the international planning competition instances. This is the first time where polynomial algorithms with meaningful bounds are shown to achieve state-of-the-art performance in planning. Practical and theoretical implications of this empirical finding are briefly sketched.

ICAPS Conference 2017 Conference Paper

Adapting Novelty to Classical Planning as Heuristic Search

Michael Katz 0001
Nir Lipovetzky
Dany Moshkovich
Alexander Tuisov

The introduction of the concept of state novelty has advanced the state of the art in deterministic online planning in Atari-like problems and in planning with rewards in general, when rewards are defined on states. In classical planning, however, the success of novelty as the dichotomy between novel and non-novel states was somewhat limited. Until very recently, novelty-based methods were not able to successfully compete with state-of-the-art heuristic search based planners. In this work we adapt the concept of novelty to heuristic search planning, defining the novelty of a state with respect to its heuristic estimate. We extend the dichotomy between novel and non-novel states and quantify the novelty degree of state facts. We then show a variety of heuristics based on the concept of novelty and exploit the recently introduced best-first width search for satisficing classical planning. Finally, we empirically show the resulting planners to significantly improve the state of the art in satisficing planning.

AAAI Conference 2017 Conference Paper

Best-First Width Search: Exploration and Exploitation in Classical Planning

Nir Lipovetzky
Hector Geffner

It has been shown recently that the performance of greedy best-ﬁrst search (GBFS) for computing plans that are not necessarily optimal can be improved by adding forms of exploration when reaching heuristic plateaus: from random walks to local GBFS searches. In this work, we address this problem but using structural exploration methods resulting from the ideas of width-based search. Width-based methods seek novel states, are not goal oriented, and their power has been shown recently in the Atari and GVG-AI video-games. We show ﬁrst that width-based exploration in GBFS is more effective than GBFS with local GBFS search (GBFS-LS), and then proceed to formulate a simple and general computational framework where standard goal-oriented search (exploitation) and widthbased search (structural exploration) are combined to yield a search scheme, best-ﬁrst width search, that is better than both and which results in classical planning algorithms that outperform the state-of-the-art planners.

IJCAI Conference 2017 Conference Paper

Handling non-local dead-ends in Agent Planning Programs

Lukas Chrpa
Nir Lipovetzky
Sebastian Sardina

We propose an approach to reason about agent planning programs with global information. Agent planning programs can be understood as a network of planning tasks, accommodating long-term goals, non-terminating behaviors, and interactive execution. We provide a technique that relies on reasoning about ``global" dead-ends and that can be incorporated to any planning-based approach to agent planning problems. In doing so, we also introduce the notion of online execution of such planning structures. We provide experimental evidence suggesting the technique yields significant benefits.

IJCAI Conference 2017 Conference Paper

Purely Declarative Action Descriptions are Overrated: Classical Planning with Simulators

Guillem Francès
Miquel Ramírez
Nir Lipovetzky
Hector Geffner

Classical planning is concerned with problems where a goal needs to be reached from a known initial state by doing actions with deterministic, known effects. Classical planners, however, deal only with classical problems that can be expressed in declarative planning languages such as STRIPS or PDDL. This prevents their use on problems that are not easy to model declaratively or whose dynamics are given via simulations. Simulators do not provide a declarative representation of actions, but simply return successor states. The question we address in this paper is: can a planner that has access to the structure of states and goals only, approach the performance of planners that also have access to the structure of actions expressed in PDDL? To answer this, we develop domain-independent, black box planning algorithms that completely ignore action structure, and show that they match the performance of state-of-the-art classical planners on the standard planning benchmarks. Effective black box algorithms open up new possibilities for modeling and for expressing control knowledge, which we also illustrate.

IJCAI Conference 2017 Conference Paper

Real--Time UAV Maneuvering via Automated Planning in Simulations

Miquel Ramírez
Michael Papasimeon
Lyndon Behnke
Nir Lipovetzky
Tim Miller
Adrian R. Pearce

The automatic generation of realistic behavior such as tactical intercepts for Unmanned Aerial Vehicles (UAV) in air combat is a challenging problem. State-of-the-art solutions propose hand-crafted algorithms and heuristics whose performance depends heavily on the initial conditions and specific aerodynamic characteristics of the UAVs involved. This demo shows the ability of domain-independent planners, embedded into simulators, to generate on-line, feed-forward, control signals that steer simulated aircraft as best suits the situation.

IJCAI Conference 2016 Conference Paper

Sequencing Operator Counts

Toby O. Davies
Adrian R. Pearce
Peter J. Stuckey
Nir Lipovetzky

Operator-counting is a recently developed framework for analysing and integrating many state-of-the-art heuristics for planning using Linear Programming. In cost-optimal planning only the objective value of these heuristics is traditionally used to guide the search. However the primal solution, i. e. the operator counts, contains useful information. We exploit this information using a SAT-based approach which given an operator-count, either finds a valid plan; or generates a generalized landmark constraint violated by that count. We show that these generalized landmarks can be used to encode the perfect heuristic, h*, as a Mixed Integer Program. Our most interesting experimental result is that finding or refuting a sequence for an operator-count is most often empirically efficient, enabling a novel and promising approach to planning based on Logic-Based Benders Decomposition (LBBD).

ICAPS Conference 2016 Conference Paper

Traps, Invariants, and Dead-Ends

Nir Lipovetzky
Christian J. Muise
Hector Geffner

We consider the problem of deriving formulas that capture traps, invariants, and dead-ends in classical planning through polynomial forms of preprocessing. An invariant is a formula that is true in the initial state and in all reachable states. A trap is a conditional invariant: once a state is reached that makes the trap true, all the states that are reachable from it will sat- isfy the trap formula as well. Finally, dead-ends are formulas that are satisfied in states that make the goal unreachable. We introduce a preprocessing algorithm that computes traps in k- DNF form that is exponential in the k parameter, and show how the algorithm can be used to precompute invariants and dead-ends. We report also preliminary tests that illustrate the effectiveness of the preprocessing algorithm for identifying dead-end states, and compare it with the identification that follows from the use of the h1 and h2 heuristics that cannot be preprocessed, and must be computed at run time.

IJCAI Conference 2015 Conference Paper

Classical Planning with Simulators: Results on the Atari Video Games

Nir Lipovetzky
Miquel Ramirez
Hector Geffner

The Atari 2600 games supported in the Arcade Learning Environment [Bellemare et al. , 2013] all feature a known initial (RAM) state and actions that have deterministic effects. Classical planners, however, cannot be used off-the-shelf as there is no compact PDDL-model of the games, and action effects and goals are not known a priori. Indeed, there are no explicit goals, and the planner must select actions on-line while interacting with a simulator that returns successor states and rewards. None of this precludes the use of blind lookahead algorithms for action selection like breadth-first search or Dijkstra’s yet such methods are not effective over large state spaces. We thus turn to a different class of planning methods introduced recently that have been shown to be effective for solving large planning problems but which do not require prior knowledge of state transitions, costs (rewards) or goals. The empirical results over 54 Atari games show that the simplest such algorithm performs at the level of UCT, the state-of-the-art planning method in this domain, and suggest the potential of width-based methods for planning with simulators when factored, compact action models are not available.

ICAPS Conference 2015 Conference Paper

Sequencing Operator Counts

Toby O. Davies
Adrian R. Pearce
Peter J. Stuckey
Nir Lipovetzky

Operator-counting is a recently developed framework for analysing and integrating many state-of-the-art heuristics for planning using Linear Programming. In cost-optimal planning only the objective value of these heuristics is traditionally used to guide the search. However the primal solution, i. e. the operator counts, contains useful information. We exploit this information using a SAT-based approach which given an operator-count, either finds a valid plan; or generates a generalized landmark constraint violated by that count. We show that these generalized landmarks can be used to encode the perfect heuristic, h*, as a Mixed Integer Program. Our most interesting experimental result is that finding or refuting a sequence for an operator-count is most often empirically efficient, enabling a novel and promising approach to planning based on Logic-Based Benders Decomposition (LBBD).

ICAPS Conference 2014 Conference Paper

Planning for Mining Operations with Time and Resource Constraints

Nir Lipovetzky
Christina N. Burt
Adrian R. Pearce
Peter J. Stuckey

We study a daily mine planning problem where, given a set of blocks we wishto mine, our task is to generate a mining sequence for the excavators suchthat blending resource constraints are met at various stages of thesequence. Such time-oriented resource constraintsare not traditionally handled well by automated planners. On the other hand, the remaining problem involves finding node-disjoint sequences withstate-dependent travel times on the arcs, which are highly challenging for a Mixed-Integer Program (MIP). In this paper, we address the problem of finding feasible sequences using a combined MIP and planning based decomposition approach. The MIP takes care of the resource constraints, and the planner solves the remaining sequence problem. We extend the notion of finding feasible sequences to finding good feasible sequences, by devising a heuristic objective function in the MIP, which improves the resulting search space for the planner. We empirically analyse the scalability of our approach on a benchmark data set, before demonstrating its effectiveness on a real world case study provided by our industry partner. These results demonstrate that by using a heuristic MIP, it is possible to obtain better makespan results with a suboptimal planner than by using an optimal planner with an uninformed MIP.

ECAI Conference 2014 Conference Paper

Width-based Algorithms for Classical Planning: New Results

Nir Lipovetzky
Hector Geffner

We have recently shown that classical planning problems can be characterized in terms of a width measure that is bounded and small for most planning benchmark domains when goals are restricted to single atoms. Two simple algorithms have been devised for exploiting this structure: Iterated Width (IW) for achieving atomic goals, that runs in time exponential in the problem width by performing a sequence of pruned breadth first searches, and Serialized IW (SIW) that uses IW in a greedy search for achieving conjunctive goals one goal at a time. While SIW does not use heuristic estimators of any sort, it manages to solve more problems than a Greedy BFS using a heuristic like hadd. Yet, it does not approach the performance of more recent planners like LAMA. In this short paper, we introduce two simple extension to IW and SIW that narrow the performance gap with state-of-the-art planners. The first involves changing the greedy search for achieving the goals one at a time, by a depth-first search that is able to backtrack. The second involves computing a relaxed plan once before going to the next subgoal for making the pruning in the breadth-first procedure less agressive, while keeping IW exponential in the width parameter. The empirical results are interesting as they follow from ideas that are very different from those used in current planners.

IJCAI Conference 2013 Conference Paper

Fair LTL Synthesis for Non-Deterministic Systems Using Strong Cyclic Planners

Fabio Patrizi
Nir Lipovetzky
Hector Geffner

We consider the problem of planning in environments where the state is fully observable, actions have non-deterministic effects, and plans must generate infinite state trajectories for achieving a large class of LTL goals. More formally, we focus on the control synthesis problem under the assumption that the LTL formula to be realized can be mapped into a deterministic Büchi automaton. We show that by assuming that action non-determinism is fair, namely that infinite executions of a nondeterministic action in the same state yield each possible successor state an infinite number of times, the (fair) synthesis problem can be reduced to a standard strong cyclic planning task over reachability goals. Since strong cyclic planners are built on top of efficient classical planners, the transformation reduces the non-deterministic, fully observable, temporally extended planning task into the solution of classical planning problems. A number of experiments are reported showing the potential benefits of this approach to synthesis in comparison with state-of-the-art symbolic methods.

PDF Details DOI

ECAI Conference 2012 Conference Paper

Width and Serialization of Classical Planning Problems

Nir Lipovetzky
Hector Geffner

We introduce a width parameter that bounds the complexity of classical planning problems and domains, along with a simple but effective blind-search procedure that runs in time that is exponential in the problem width. We show that many benchmark domains have a bounded and small width provided that goals are restricted to single atoms, and hence that such problems are provably solvable in low polynomial time. We then focus on the practical value of these ideas over the existing benchmarks which feature conjunctive goals. We show that the blind-search procedure can be used for both serializing the goal into subgoals and for solving the resulting problems, resulting in a 'blind' planner that competes well with a best-first search planner guided by state-of-the-art heuristics. In addition, ideas like helpful actions and landmarks can be integrated as well, producing a planner with state-of-the-art performance.

IJCAI Conference 2011 Conference Paper

Computing Infinite Plans for LTL Goals Using a Classical Planner

Fabio Patrizi
Nir Lipovetzky
Giuseppe De Giacomo
Hector Geffner

Classical planning has been notably successful in synthesizing finite plans to achieve states where propositional goals hold. In the last few years, classical planning has also been extended to incorporate temporally extended goals, expressed in temporal logics such as LTL, to impose restrictions on the state sequences generated by finite plans. In this work, we take the next step and consider the computation of infinite plans for achieving arbitrary LTL goals. We show that infinite plans can also be obtained efficiently by calling a classical planner once over a classical planning encoding that represents and extends the composition of the planning domain and the Buchi automaton representing the goal. This compilation scheme has been implemented and a number of experiments are reported.

PDF Details DOI

ICAPS Conference 2011 Conference Paper

Searching for Plans with Carefully Designed Probes

Nir Lipovetzky
Hector Geffner

We define a probe to be a single action sequence computedgreedily from a given state that either terminates in the goalor fails. We show that by designing these probes carefullyusing a number of existing and new polynomial techniquessuch as helpful actions, landmarks, commitments, and con-sistent subgoals, a single probe from the initial state solvesby itself 683 out of 980 problems from previous IPCs, a num-ber that compares well with the 627 problems solved by FFin EHC mode, with similar times and plan lengths. We alsoshow that by launching one probe from each expanded statein a standard greedy best first search informed by the addi-tive heuristic, the number of problems solved jumps to 900(92%), as opposed to FF that solves 827 problems (84%), and LAMA that solves 879 (89%). The success of probessuggests that many domains can be solved easily once a suit-able serialization of the landmarks is found, an observationthat may open new connections between recent work in plan-ning and more classical work concerning goal serializationand problem decomposition in planning and search.

ICAPS Conference 2009 Conference Paper

Inference and Decomposition in Planning Using Causal Consistent Chains

Nir Lipovetzky
Hector Geffner

Current state-of-the-art planners solve problems, easy and hard alike, by search, expanding hundreds or thousands of nodes. Yet, given the ability of people to solve easy problems and to explain their solutions, it seems that an essential inferential component may be missing. The reasons expressed by people for selecting actions appear to be related to causal chains: sequences of causal links ai → pi + 1, i = 0, .. ., n – 1, such that a0 is applicable in the current state, pi is a precondition of action ai, and pn is a goal. Some of these causal chains or paths appear to be good, some bad, others appear to be impossible. In this work, we focus on such paths and develop three techniques for performing inference over them from which a path-based planner is obtained. We define the conditions under which a path is consistent, provide an heuristic estimate of the cost of achieving the goal along a consistent path, and introduce a planning algorithm that uses paths as decomposition backbones. The resulting planner, called C3, is not complete and does not perform as well as recent planners that carry extensive but extremely efficient searches such as LAMA, but is competitive with FF and in particular, with FF running in EHC mode which yields very focused but incomplete searches, and thus provides, a more apt comparison. Moreover, many domains are solved backtrack-free, with no search at all, suggesting that planning with paths may be a meaningful idea both cognitively and computationally.