Capturing and exploiting structural knowledge of planning problems has shown to be a successful strategy for making the planning process more efficient. Plans can be decomposed into its constituent coherent subplans, called blocks, that encapsulate some effects and preconditions, reducing interference and thus allowing more deordering of plans. According to the nature of blocks, they can be straightforwardly transformed into useful macro-operators (shortly, macros). Macros are well known and widely studied kind of structural knowledge because they can be easily encoded in the domain model and thus exploited by standard planning engines. In this paper, we introduce a method, called BloMa, that learns domain-specific macros from plans, decomposed into macro-blocks which are extensions of blocks, utilising structural knowledge they capture. In contrast to existing macro learning techniques, macro-blocks are often able to capture high-level activities that form a basis for useful longer macros (i.e. those consisting of more original operators). Our method is evaluated by using the IPC benchmarks with state-of-the-art planning engines, and shows considerable improvement in many cases.

To engage diverse agents in cooperative behavior, it is important, even necessary, to provide algorithms that do not reveal information that is private or proprietary.A number of recent planning algorithms enable agents to plan together for shared goals without disclosing information about their private state and actions. But these algorithms lack clear and formal privacy guarantees: the fact that they do not require agents to explicitly reveal private information, does not imply that such information cannot be deduced. The main contribution of this paper is an enhanced version of the distributed forward-search planning framework of Nissim and Brafman that reveals less information than the original algorithm, and the first, to our knowledge, discussion and formal proof of privacy guarantees for distributed planning and search algorithms.

Non-linear continuous change is common in real-world problems, especially those that model physical systems. We present an algorithm which builds upon existent temporal planning techniques based on linear programming to approximate non-linear continuous monotonic functions. These are integrated through a semantic attachment mechanism, allowing external libraries or functions that are difficult to model in native PDDL to be evaluated during the planning process. A new planning system implementing this algorithm was developed and evaluated. Results show that the addition of this algorithm to the planning process can enable it to solve a broader set of planning problems.

This paper addresses two classes of different, yet interrelated optimization problems. The first class of problems involves a robot that must locate a hidden target in an environment that consists of a set of concurrent rays. The second class pertains to the design of interruptible algorithms by means of a schedule of contract algorithms. We study several variants of these families of problems, such as searching and scheduling with probabilistic considerations, redundancy and fault-tolerance issues, randomized strategies, and trade-offs between performance and preemptions. For many of these problems we present the first known results that apply to multi-ray and multi-problem domains. Our objective is to demonstrate that several well-motivated settings can be addressed using a common approach.

Monte-Carlo Tree Search (MCTS) algorithms such as UCT are an attractive online framework for solving planning under uncertainty problems modeled as a Markov Decision Process. However, MCTS search trees are constructed in flat state and action spaces, which can lead to poor policies for large problems. In a separate research thread, domain abstraction techniques compute symmetries to reduce the original MDP. This can lead to significant savings in computation, but these have been predominantly implemented for offline planning. This paper makes two contributions. First, we define the ASAP (Abstraction of State-Action Pairs) framework, which extends and unifies past work on domain abstractions by holistically aggregating both states and state-action pairs — ASAP uncovers a much larger number of symmetries in a given domain. Second, we propose ASAP-UCT, which implements ASAP-style abstractions within a UCT framework combining strengths of online planning with domain abstractions. Experimental evaluation on several benchmark domains shows up to 26% improvement in the quality of policies obtained over existing algorithms.

Hierarchical Task Network (HTN) planning with Task Insertion (TIHTN planning) is a formalism that hybridizes classical planning with HTN planning by allowing the insertion of operators from outside the method hierarchy. This additional capability has some practical benefits, such as allowing more flexibility for design choices of HTN models: the task hierarchy may be specified only partially, since "missing required tasks" may be inserted during planning rather than prior planning by means of the (predefined) HTN methods. While task insertion in a hierarchical planning setting has already been applied in practice, its theoretical properties have not been studied in detail, yet — only EXPSPACE membership is known so far. We lower that bound proving NEXPTIME-completeness and further prove tight complexity bounds along two axes: whether variables are allowed in method and action schemas, and whether methods must be totally ordered. We also introduce a new planning technique called acyclic progression, which we use to define provably efficient TIHTN planning algorithms.

This choice, which is also related to the finitary and infinitary The model-checking problem for Resource Agent semantics of [Bulling and Farwer, 2010], stipulates whether Logic is known to be undecidable. We review existing in every model, agents always have a choice of doing nothing (un)decidability results and identify a significant (executing an idle action) that produces and consumes fragment of the logic for which model checking no resources [Alechina et al., 2014]. Apart from the technical is decidable. We discuss aspects which makes convenience for model-checking (intuitively it implies model checking decidable and prove undecidability that any strategy to satisfy a next or until formula only needs of two open fragments over a class of models in to ensure the relevant subformula becomes true after finitely which agents always have a choice of doing nothing.

We eliminate symmetry from a problem before searching for a plan. The planning problem with symmetries is decomposed into a set of isomorphic subproblems. One plan is computed for a small planning problem posed by a descriptive quotient, a description of any such subproblem. A concrete plan is synthesized by concatenating instantiations of that one plan for each subproblem. Our approach is sound.

Ontology matching is the process of finding semantic correspondences between entities from different ontologies. As an effective solution to linking different heterogeneous ontologies, ontology matching has attracted considerable attentions in recent years. In this paper, we propose a novel graph-based approach to ontology matching problem. Different from previous work, we formulate ontology matching as a random walk process on the association graph constructed from the to-be-matched ontologies. In particular, two variants of the conventional random walk process, namely, Affinity-Preserving Random Walk (APRW) and Mapping-Oriented Random Walk (MORW), have been proposed to alleviate the adverse effect of the false-mapping nodes in the association graph and to incorporate the 1-to-1 matching constraints presumed in ontology matching, respectively. Experiments on the Ontology Alignment Evaluation Initiative (OAEI) datasets show that our approach achieves a competitive performance when compared with state-of-the-art systems, even though our approach does not utilize any external resources.

Building ontologies is a difficult task requiring skills in logics and ontological analysis. Domain experts usually reach as far as organizing a set of concepts into a hierarchy in which the semantics of the relations is under-specified. The categorization of Wikipedia is a huge concept hierarchy of this form, covering a broad range of areas. We propose an automatic method for bootstrapping domain ontologies from the categories of Wikipedia. The method first selects a subset of concepts that are relevant for a given domain. The relevant concepts are subsequently split into classes and individuals, and, finally, the relations between the concepts are classified into subclass_of, instance_of, part_of, and generic related_to. We evaluate our method by generating ontology skeletons for the domains of Computing and Music. The quality of the generated ontologies has been measured against manually built ground truth datasets of several hundred nodes.