The fundamental reasoning problem in RCC-8 is deciding In contrast to the synthetic RCC-8 networks that have the consistency of a set of constraints Θ, i.e., whether there been used in the literature for evaluating the aforementioned is a spatial configuration where the relations between the reasoners, the real-world networks of Table 1 are very sparse regions can be described by Θ. Traditionally in qualitative and one to two orders of magnitude larger. The labels on spatial reasoning (QSR) consistency of such sets is decided their edges contain 1 or 2 base RCC-8 relations forming a by a backtracking algorithm which optionally uses a pathconsistency disjunction. This kind of networks have not been employed algorithm as a preprocessing step for forward in any experimental evaluation of RCC-8 reasoners with the checking. In general, this problem is NPcomplete (Renz exception of (Sioutis and Koubarakis 2012) in which the network and Nebel 1999). However it has been shown in (Renz 1999) adm1 has been used. Typically, the literature focuses that there are tractable subsets of RCC-8 for which the consistency on quite smaller networks (20 to 1000 nodes) with an average problem can be decided by path-consistency. of 4 base RCC-8 relations per edge, and an average Table 1 depicts the characteristics of some real-world node degree ranging from 4 to 20. Deciding the consistency RCC-8 networks recording the topological relations between of real-world networks is a very important task. Inconsistencies administrative regions in Europe (networks nuts, might arise because their RCC-8 relations are computed adm1, and adm2) and the world (networks gadm1 and based on the geometries of geographical objects which gadm2), and the performance of the following reasoners often have not been captured correctly (e.g., overlapping geometries regarding consistency checking: Renz-Nebel01 (Renz and between two regions that in principle are externally Nebel 2001), GQR-1500 (Gantner, Westphal, and Woelfl connected). This is the case for the networks gadm1 and 2008; Westphal and Hué 2012), PPyRCC8 (Sioutis and gadm2.

Stochastic local search (SLS) algorithms have shown effectiveness on satisfiable instances of the Boolean satisfiability (SAT) problem. However, their performance is still unsatisfactory on random k-SAT at the phase transition, which is of significance and is one of the empirically hardest distributions of SAT instances. In this paper, we propose a new heuristic called DCCA, which combines two configuration checking (CC) strategies with different definitions of configuration in a novel way. We use the DCCA heuristic to design an efficient SLS solver for SAT dubbed DCCASat. The experiments show that the DCCASat solver significantly outperforms a number of state-of-the-art solvers on extensive random k-SAT benchmarks at the phase transition. Moreover, DCCASat shows good performance on structured benchmarks, and a combination of DCCASat with a complete solver achieves state-of-the-art performance on structured benchmarks.

In this paper we propose a novel DCOP algorithm, called DJAO, that is able toefficiently find a solution with low communication overhead; this algorithm can be used for optimal and bounded approximate solutions by appropriately setting the error bounds. Our approach builds on distributed junction trees used in Action-GDL to represent independence relationsamong variables. We construct an AND/OR search space based on these junction trees.This new type of search space results in higher degrees for each OR node, consequently yielding a more efficient search graph in the distributed settings. DJAO uses a branch-and-bound search algorithm to distributedly find solutions within this search graph. We introduce heuristics to compute the upper and lower boundestimates that the search starts with, which is integral to our approach for reducing communication overhead. We empirically evaluate our approach in various settings.

Bi-Objective Combinatorial Optimization problems are ubiquitous in real-world applications and designing approaches to solve them efficiently is an important research area of Artificial Intelligence. In Constraint Programming, the recently introduced bi-objective Pareto constraint allows one to solve bi-objective combinatorial optimization problems exactly. Using this constraint, every non-dominated solution is collected in a single tree-search while pruning sub-trees that cannot lead to a non-dominated solution. This paper introduces a simpler and more efficient filtering algorithm for the bi-objective Pareto constraint. The efficiency of this algorithm is experimentally confirmed on classical bi-objective benchmarks.

We present three new filtering algorithms for the Disjunctive constraint that all have a linear running time complexity in the number of tasks. The first algorithm filters the tasks according to the rules of the time tabling. The second algorithm performs an overload check that could also be used for the Cumulative constraint. The third algorithm enforces the rules of detectable precedences. The two last algorithms use a new data structure that we introduce and that we call the time line. This data structure provides many constant time operations that were previously implemented in logarithmic time by the Theta-tree data structure. Experiments show that these new algorithms are competitive even for a small number of tasks and outperform existing algorithms as the number of tasks increases.

In this paper we address the planning problem of a robot searching for multiple residents in a retirement home in order to remind them of an upcoming multi-person recreational activity before a given deadline. We introduce a novel Multi-User Schedule Based (M-USB) Search approach which generates a high-level-plan to maximize the number of residents that are found within the given time frame. From the schedules of the residents, the layout of the retirement home environment as well as direct observations by the robot, we obtain spatio-temporal likelihood functions for the individual residents. The main contribution of our work is the development of a novel approach to compute a reward to find a search plan for the robot using: 1) the likelihood functions, 2) the availabilities of the residents, and 3) the order in which the residents should be found. Simulations were conducted on a floor of a real retirement home to compare our proposed M-USB Search approach to a Weighted Informed Walk and a Random Walk. Our results show that the proposed M-USB Search finds residents in a shorter amount of time by visiting fewer rooms when compared to the other approaches.

In heterogeneous multi-robot teams, robustness and flexibility are increased by the diversity of the robots, each contributing different capabilities. Yet platform-independence is desirable when planning actions for the various robots. We propose a platform-independent model of robot capabilities which we use as a planning domain. We extend existing planning techniques to support two requirements: generating new objects during planning; and, required concurrency of actions due to data flow which can be cyclic. The first requires online action instantiation, the second a small extension of the Planning Domain Definition Language (PDDL): allowing predicates in continuous effects. We evaluate the planner on benchmark domains and present results on an example object transportation task in simulation.

Monte Carlo tree search (MCTS) algorithms are a popular approach to online decision-making in Markov decision processes (MDPs). These algorithms can, however, perform poorly in MDPs with high stochastic branching factors. In this paper, we study state aggregation as a way of reducing stochastic branching in tree search. Prior work has studied formal properties of MDP state aggregation in the context of dynamic programming and reinforcement learning, but little attention has been paid to state aggregation in MCTS. Our main result is a performance loss bound for a class of value function-based state aggregation criteria in expectimax search trees. We also consider how to construct MCTS algorithms that operate in the abstract state space but require a simulator of the ground dynamics only. We find that trajectory sampling algorithms like UCT can be adapted easily, but that sparse sampling algorithms present difficulties. As a proof of concept, we experimentally confirm that state aggregation can improve the finite-sample performance of UCT.

Conformant probabilistic planning (CPP) differs from conformant planning (CP) by two key elements: the initial belief state is probabilistic,and the conformant plan must achieve the goal with probability $\geq\theta$, for some $0<\theta\leq 1$. In earlier work we observed that one can reduce CPP to CP by finding a set of initial states whose probability $\geq\theta$, for whicha conformant plan exists. In previous solvers we used the underlying planner to select this set of states and to plan for them simultaneously. Here we suggest an alternative approach: start with relevance analysis to determine a promising set of initial states on which to focus. Then, call an off-the-shelf conformant planner to solve the resulting problem. This approach has a number of advantages. First, instead of depending on the heuristic function to select the set of initial states,we can introduce specific, efficient relevance reasoning techniques. Second, we can benefit from optimizations used by conformant planners that are unsound when applied to the original CPP. Finally, we are free to use any existing (or new) CP solver. Consequently, the new planner dominates previous solvers on almost all domains and scales to instances that were not solved before.

A wide range of robotic missions contain actions that exhibit looping behavior. Examples of these actions include picking fruit in agriculture, pick-and-place tasks in manufacturing and search patterns in robotic search or survey missions. These looping actions often have a range of acceptable values for the number of loops and a preference function over them. For example, during robotic survey missions, the information gain is expected to increase with the number of loops in a search pattern. Since these looping actions also take time, which is typically bounded, there is a challenge of maximizing utility while respecting time constraints. In this paper, we introduce the Looping Temporal Problem with Preference (LTPP) as a simple parameterized extension of a simple temporal problem. In addition, we introduce a scheduling algorithm for LTPPs which leverages the structure of the problem to find the optimal solution efficiently. We show more than an order of magnitude improvement in run-time over current scheduling techniques and framing a LTPP as a MINLP.