Search

This paper introduces a general approach for synthesizing procedural models of the state-transitions of a given discrete system. The approach is general in that it accepts different target languages for modeling the state-transitions of a discrete system; different model acquisition tasks with different target languages, such as the synthesis of STRIPS action models, or the update rule of a cellular automaton, fit as particular instances of our general approach. We follow an inductive approach to synthesis meaning that a set of examples of state-transitions, represented as (pre-state, action, post-state) tuples, are given as input. The goal is to synthesize a structured program that, when executed on a given pre-state, outputs its associated post-state. Our synthesis method implements a combinatorial search in the space of well-structured terminating programs that can be built using a Random-Access Machine (RAM), with a minimalist instruction set, and a finite amount of memory. The combinatorial search is guided with functions that asses the complexity of the candidate programs, as well as their fitness to the given input set of examples., Comment: Conference paper accepted at ECAI 2023

Planning as heuristic search is one of the most successful approaches to classical planning but unfortunately, it does not extend trivially to Generalized Planning (GP). GP aims to compute algorithmic solutions that are valid for a set of classical planning instances from a given domain, even if these instances differ in the number of objects, the number of state variables, their domain size, or their initial and goal configuration. The generalization requirements of GP make it impractical to perform the state-space search that is usually implemented by heuristic planners. This paper adapts the planning as heuristic search paradigm to the generalization requirements of GP, and presents the first native heuristic search approach to GP. First, the paper introduces a new pointer-based solution space for GP that is independent of the number of classical planning instances in a GP problem and the size of those instances (i.e. the number of objects, state variables and their domain sizes). Second, the paper defines a set of evaluation and heuristic functions for guiding a combinatorial search in our new GP solution space. The computation of these evaluation and heuristic functions does not require grounding states or actions in advance. Therefore our GP as heuristic search approach can handle large sets of state variables with large numerical domains, e.g.~integers. Lastly, the paper defines an upgraded version of our novel algorithm for GP called Best-First Generalized Planning (BFGP), that implements a best-first search in our pointer-based solution space, and that is guided by our evaluation/heuristic functions for GP., Comment: Under review in the Artificial Intelligence Journal (AIJ)

The paper introduces a novel representation for Generalized Planning (GP) problems, and their solutions, as C++ programs. Our C++ representation allows to formally proving the termination of generalized plans, and to specifying their asymptotic complexity w.r.t. the number of world objects. Characterizing the complexity of C++ generalized plans enables the application of a combinatorial search that enumerates the space of possible GP solutions in order of complexity. Experimental results show that our implementation of this approach, which we call BFGP++, outperforms the previous GP as heuristic search approach for the computation of generalized plans represented as compiler-styled programs. Last but not least, the execution of a C++ program on a classical planning instance is a deterministic grounding-free and search-free process, so our C++ representation allows us to automatically validate the computed solutions on large test instances of thousands of objects, where off-the-shelf classical planners get stuck either in the pre-processing or in the search., Comment: Accepted at sixth workshop on Generalization in Planning at IJCAI-ECAI 2022

Although heuristic search is one of the most successful approaches to classical planning, this planning paradigm does not apply straightforwardly to Generalized Planning (GP). This paper adapts the planning as heuristic search paradigm to the particularities of GP, and presents the first native heuristic search approach to GP. First, the paper defines a program-based solution space for GP that is independent of the number of planning instances in a GP problem, and the size of these instances. Second, the paper defines the BFGP algorithm for GP, that implements a best-first search in our program-based solution space, and that is guided by different evaluation and heuristic functions., Comment: Extended abstract accepted at IJCAI-22 Sister Conferences Best Paper Track. arXiv admin note: substantial text overlap with arXiv:2103.14434

Landmarks are one of the most effective search heuristics for classical planning, but largely ignored in generalized planning. Generalized planning (GP) is usually addressed as a combinatorial search in a given space of algorithmic solutions, where candidate solutions are evaluated w.r.t.~the instances they solve. This type of solution evaluation ignores any sub-goal information that is not explicit in the representation of the planning instances, causing plateaus in the space of candidate generalized plans. Furthermore, node expansion in GP is a run-time bottleneck since it requires evaluating every child node over the entire batch of classical planning instances in a GP problem. In this paper we define a landmark counting heuristic for GP (that considers sub-goal information that is not explicitly represented in the planning instances), and a novel heuristic search algorithm for GP (that we call PGP) and that progressively processes subsets of the planning instances of a GP problem. Our two orthogonal contributions are analyzed in an ablation study, showing that both improve the state-of-the-art in GP as heuristic search, and that both benefit from each other when used in combination., Comment: Accepted at SoCS 2022 (extended version)

In social commerce, users dialogue with each other on the topics related to the providers' products. However, the language customers use may vary from the language vendors use on their e-commerce websites and product descriptions. This situation can lead to possible misunderstandings in the social dialogue between customers, and incidental costs in the dialogue between customers and vendors. One possible reason for this difference is that words used by customers may have different meanings compared to those used by product description writers. We present a novel approach to measure this potential lexical-semantic gap for various e-commerce domains using an information-theoretical approach based on a large corpus of user reviews and product descriptions. Additionally, we use neural word embeddings to identify words with the highest semantic drift between reviews and descriptions as a tool to construct a ground truth for the task. We found that low levels of lexical-semantic gap are related to better customer satisfaction. Besides, this work is a step towards a better understanding of the effect of the use of language in e-commerce and social commerce. Potential applications of this technology could lead to better communication between customers and improvements in customer satisfaction, services, and revenue. Furthermore, this study opens up perspectives for applications in other domains with relationships beyond client-vendor, such as citizen-government and patient-healthcare system.