This paper considers planning missions for a fleet of robots with limited energy. Each robot has size, heading, and velocity and its motion is described by non-linear differential equations. The dynamics of movements, existing obstacles, multiple robots, and waypoints are additional challenges, as the combined task and motion planning procedure prevents collisions. On their long-term missions, robots have to visit several waypoints in a cost-minimizing manner to satisfy the overall mission task. The robots consume energy and have to be recharged. The framework guides expanding a motion tree via a state projection to a discrete problem, whose solutions serve as search heuristics. Our experiments highlight that despite all these challenges, even sizable problem tasks can be solved even for complex environments.

In imitation learning for planning, parameters of heuristic functions are optimized against a set of solved problem instances. This work revisits the necessary and sufficient conditions of strictly optimally efficient heuristics for forward search algorithms, mainly A* and greedy best-first search, which expand only states on the returned optimal path. It then proposes a family of loss functions based on ranking tailored for a given variant of the forward search algorithm. Furthermore, from a learning theory point of view, it discusses why optimizing cost-to-goal h* is unnecessarily difficult. The experimental comparison on a diverse set of problems unequivocally supports the derived theory.

Effective planning while competing for limited resources is crucial in many real-world applications such as on-demand transport companies competing for passengers. Planning techniques therefore have to take into account possible actions of an adversarial agent. Such a challenge that can be tackled by leveraging game-theoretical methods such as Double Oracle. This paper aims at the scalability issues arising from combining planning techniques with Double Oracle. In particular, we propose an abstraction-based heuristic for deciding how resources will be collected (e.g. which car goes for which passenger and in which order) and we propose a method for decomposing planning tasks into smaller ones (e.g. generate plans for each car separately). Our empirical evaluation shows that our proposed approach considerably improves scalability compared to the state-of-the-art techniques.

Sampling-based motion planning algorithms such as Rapidly exploring Random Trees (RRTs) have been used in robotic applications for a long time. In this paper, we propose a method that combines deep learning with RRT* method. We use a neural network to learn a sample strategy for RRT*.We evaluate Deep RRT* in a collection of 2D scenarios. The results demonstrate that our algorithm could find collision-free paths efficiently and fast, and can be generalized to unseen environments.

This paper proposes knowledge-based paranoia search (KBPS) to find forced wins in the card game Skat; an internationally played card game, and likely one of the most interesting card games for three players. It combines efficient partial information game-tree search with knowledge representation and reasoning. This worst-case analysis, initiated after a small number of tricks, leads to a prioritized choice of cards. We provide variants of KBPS for the declarer and the opponents, and an approximation to find a forced win against most worlds in the belief space. Replaying thousands of expert games, our evaluation indicates that the AIs with the new algorithms perform better than humans in their play, achieving an average score of over 1,000 points in the agreed standard for evaluating Skat tournaments, the extended Seeger system.

Effective plan generation in adversarial environments has to take into account possible actions of adversary agents, i.e., the agent should know what the competitor will likely do. In this paper we propose a novel approach for estimating strategies of the adversary, sampling actions that interfere with the agent's ones. The estimated competitor strategies are used in plan generation by considering that agent's actions have to be applied prior to the ones of the competitor, whose estimated times dictate the agent's deadlines. Missing these deadlines entails additional plan cost.

We look at several proposals to engineer the set of fundamental searching and sorting algorithms. Aspects are improving locality of disk access and cache access, the efficiency tuning by reducing the number of branch mispredictions, and reducing at leading factors hidden in the Big-Oh notation. These studies in algorithm engineering, in turn, lead to exiting new algorithm designs. On the practical side, we will establish that efficient sorting and searching algorithms are in tight collaboration, as sorting is used for finding duplicates in disk-based search, and heap structures designed for efficient graph search can be exploited in classical and adaptive sorting. We indicate the effects of engineered sorting and searching for combined task and motion planning.

The two most prominent solutions for the sorting problem are Quicksort and Mergesort. While Quicksort is very fast on average, Mergesort additionally gives worst-case guarantees, but needs extra space for a linear number of elements. Worst-case efficient in-place sorting, however, remains a challenge: the standard solution, Heapsort, suffers from a bad cache behavior and is also not overly fast for in-cache instances. In this work we present median-of-medians QuickMergesort (MoMQuickMergesort), a new variant of QuickMergesort, which combines Quicksort with Mergesort allowing the latter to be implemented in place. Our new variant applies the median-of-medians algorithm for selecting pivots in order to circumvent the quadratic worst case. Indeed, we show that it uses at most n log n + 1.6n comparisons for n large enough. We experimentally confirm the theoretical estimates and show that the new algorithm outperforms Heapsort by far and is only around 10% slower than Introsort (std::sort implementation of stdlibc++), which has a rather poor guarantee for the worst case. We also simulate the worst case, which is only around 10% slower than the average case. In particular, the new algorithm is a natural candidate to replace Heapsort as a worst-case stopper in Introsort.

After impressive successes in deterministic and fully-observable board games to significantly outclass humans, game playing research shifts towards non-deterministic and imperfect information card games, where humans are still persistently better. In this paper we devise a player that challenges human supremacy in Skat. We provide a complete player for playing selected variants of the game, with effective solutions for bidding and Skat putting, extracting knowledge from several million games. For trick play we combine expert rules with engineered tree exploration for optimal open card play. For dealing with uncertainty especially in Ouvert games we search the belief space.

Abstract Toward enhancing automation, this paper proposes an efficient approach for multi‐group motion planning, where the set of goals is divided intokgroups and the objective is to compute a collision‐free and dynamically feasible trajectory that enables a virtual vehicle to reach at least one goal from each group. The approach works with ground and aerial vehicles operating in complex environments containing numerous obstacles. In addition to modeling the vehicle dynamics by differential equations, the approach can use physics‐based game engines, which provide an increased level of realism. The approach is based on a hybrid search that uses generalized traveling salesman tours over a probabilistic roadmap to effectively guide the sampling‐based expansion of a motion tree. As the motion tree is expanded with collision‐free and dynamically feasible trajectories, tours are adjusted based on a partition of the motion tree into equivalence classes. This gives the approach the flexibility to discover new tours that avoid collisions and are compatible with the vehicle dynamics. Comparisons to related work show significant improvements both in terms of runtime and solution length. Copyright © 2016 John Wiley & Sons, Ltd.

In this work, we propose the application of the SPIN software model checker to a multiagent system that controls the industrial production of goods. The flow of material is buffered on a production line with assembling stations. As the flow of material is asynchronous at each station, queuing is required as long as buffers provide waiting room. Besides validating the design of the system, the core objective of this work is to find concurrent plans that optimize the throughput of the system. In the mapping of the production system to the model checker, we model the production line as a set of communicating processes, with the movement of items modeled as channels. Experiments show that the model checker is able to analyze the system, subject to the partial ordering of the product parts. It derives valid and optimized plans with several thousands of steps using constraint branching in branch-and-bound search. We compare the results with a randomized exploration based on recent advances in Monte Carlo search.

In this paper we solve fundamental graph optimization problems like Maximum Clique and Minimum Coloring with recent advances of Monte-Carlo Search. The optimization problems are implemented as single-agent games in a generic state-space search framework, roughly comparable to what is encoded in PDDL for an action planner.

We study the problem of constructing a binary heap in an array using only a small amount of additional space. Let N denote the size of the input, M the capacity of the cache, and B the width of the cache lines of the underlying computer, all measured as numbers of elements. We show that there exists an in-place heap-construction algorithm that runs in Θ(N) worst-case time and performs at most 1.625N+o(N) element comparisons, 1.5N+o(N) element moves, N/B+O(N/M·lgN) cache misses, and 1.375N+o(N) branch mispredictions. The same bound for the number of element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their algorithm requires Θ(N) pointers. For a tuning parameter S, the idea is to divide the input into a top tree of size Θ(N/S) such that each of its leaves root a bottom tree of size Θ(S)⁠. When S=Θ(lgN/lglgN)⁠, we can convert the bottom trees into heaps one by one by packing the extra space needed in a few words, and subsequently use Floyd's sift-down procedure to adjust the heap order at the upper levels. In addition to our theoretical findings, we also compare different heap-construction alternatives in practice.

Since the work of Kaligosi and Sanders (2006), it is well-known that Quicksort - which is commonly considered as one of the fastest in-place sorting algorithms - suffers in an essential way from branch mispredictions. We present a novel approach to address this problem by partially decoupling control from data flow: in order to perform the partitioning, we split the input in blocks of constant size (we propose 128 data elements); then, all elements in one block are compared with the pivot and the outcomes of the comparisons are stored in a buffer. In a second pass, the respective elements are rearranged. By doing so, we avoid conditional branches based on outcomes of comparisons at all (except for the final Insertionsort). Moreover, we prove that for a static branch predictor the average total number of branch mispredictions is at most epsilon n log n + O(n) for some small epsilon depending on the block size when sorting n elements. Our experimental results are promising: when sorting random integer data, we achieve an increase in speed (number of elements sorted per second) of more than 80% over the GCC implementation of C++ std::sort. Also for many other types of data and non-random inputs, there is still a significant speedup over std::sort. Only in few special cases like sorted or almost sorted inputs, std::sort can beat our implementation. Moreover, even on random input permutations, our implementation is even slightly faster than an implementation of the highly tuned Super Scalar Sample Sort, which uses a linear amount of additional space.

In this paper we propose the application of a model checker to evaluate a multiagent system that controls the industrial production of autonomous products. As the flow of material is asynchronous at each station, queuing effects arise as long as buffers provide waiting room. Besides validating the design of the system, the core objective of this work is to find plans that optimize the throughput of the system. Instead of mapping the multiagent system directly to the model checker, we model the production line as a set of communicating processes, with the movement of items modeled as communication channels. Experiments shows that the model checker is able to analyze the movements of autonomous products for the model, subject to the partial ordering of the product parts. It derives valid and optimized plans with several thousands of steps using constraint branch-and-bound.

The cost-optimal track of the international planning competition in 2014 has seen an unexpected outcome. Different to the precursing competition in 2011, where explicit-state heuristic search planning scored best, advances in the state-set exploration with BDDs showed a significant lead. In this paper we review the outcome of the competition, briefly looking into the internals of the competing systems.

The paper considers solving the multiple sequence alignment, a combinatorial challenge in computational biology, where several DNA RNA, or protein sequences are to be arranged for high similarity. The proposal applies randomized Monte-Carlo tree search with nested rollouts and is able to improve the solution quality over time. Instead of learning the position of the letters, the approach learns a policy for the position of the gaps. The Monte-Carlo beam search algorithm we have implemented has a low memory overhead and can be invoked with constructed or known initial solutions. Experiments in the BAliBASE benchmark show promising results in improving state-of-the-art alignments.

Transporting goods by courier and express services increases the service quality through short transit times and satisfies individual demands of customers. Determining the optimal route for a vehicle to satisfy transport requests while minimizing the total cost refers to the Single Vehicle Pickup and Delivery Problem. Beside time and distance objectives, in real world operations it is mandatory to consider further constraints such as time windows and the capacity of the vehicle. This paper presents a novel approach to solve Single Vehicle Pickup and Delivery Problems with time windows and capacity constraints by applying Nested Monte-Carlo Search (NMCS). NMCS is a randomized exploration technique which has successfully solved complex combinatorial search problems. To evaluate the approach, we apply benchmarks instances with up to 400 cities which have to be visited. The effects of varying the number of iterations and the search level are investigated. The results reveal, that the algorithm computes state-of-the-art solutions and is competitive with other approaches.

This paper pursues multi-goal motion planning, where the overall set of goals is divided into k groups and the virtual agent needs to visit at least one goal per group. We have developed a combined task and motion-planning approach which can work with ground and aerial vehicles whose motions are simulated by differential equations or by physics-based game engines. The proposed approach is based on a hybrid search, where the expansion of a motion tree in the continuous state space is guided by heuristic costs and generalized traveling salesman tours computed over a discrete abstraction. The discrete abstraction is obtained via a probabilistic roadmap constructed over a low-dimensional configuration space resulting from a simplified problem setting. By capturing the connectivity of the free configuration space and connecting the goals, the roadmap provides generalized traveling salesman tours that effectively guide the motion-tree expansion. Experiments demonstrate that the approach not only improves previous methodologies in terms of runtime and solution length but also that it is scalable with respect to both the number of goals and groups.

Nearest neighbour searches in the image plane are among the most frequent problems in a variety of computer vision and image processing tasks. They can be used to replace missing values in image filtering, or to group close objects in image segmentation, or to access neighbouring points of interest in feature extraction. In particular, we address two nearest neighbour problems: The nearest neighbour problem is usually stated independently of the application as returning the point p ∈ S,S = {(x1,y1), . . . ,(xn,yn)} that minimises the Euclidean distance ||p− q||2 to a query point q = (x,y). The simple solution of a linear scan comprises a comparison of q to all elements of S, which is too time-consuming for most applications, especially those with real-time requirements. If the nearest neighbour p ∈ S must be found for every coordinate q ∈ I of an image I = {(0,0),(0,1),(0,2), . . . ,(W,H)} of width W and height H, we obtain the all nearest neighbours problem. This problem occurs frequently in modern saliency based approaches, where only robustly detectable image regions are processed (for example in SIFT). In this paper, we introduce an approximate solution to solve these problems that is based on using a space filling curve. The central idea of the proposed approach is to map the image plane to one dimension using the Hilbert curve (Fig. 1). The nearest-neighbour problem is then solved efficiently in one dimension and mapped back to the 2D-plane.

Symbolic search using BDDs usually saves huge amounts of memory, while in some domains its savings are moderate at best. It is an open problem to determine if BDDs work well for a certain domain. Motivated by finding evidences for BDD growths for state space search, in this paper we are concerned with symbolic search in the domain of Connect Four. We prove that there is a variable ordering for which the set of all possible states – when continuing after a terminal state has been reached – can be represented by polynomial sized BDDs, whereas the termination criterion leads to an exponential number of nodes in the BDD given any variable ordering.

Symbolic search with BDDs has shown remarkable performance for cost-optimal deterministic planning by exploiting a succinct representation and exploration of state sets. In this paper we enhance BDD-based planning by applying a combination of domain-independent search techniques: the optimization of the variable ordering in the BDD by approximating the linear arrangement problem, pattern selection for improved construction of search heuristics in form of symbolic partial pattern databases, and a decision procedure for the amount of bidirection in the symbolic search process.

In this paper we improve solving two-player games by computing the game-theoretical value of every reachable state. A graphics processing unit located on the graphics card is used as a co-processor to accelerate the solution process. We exploit perfect hash functions to store the game states efficiently in memory and to transfer their ordinal representation between the host and the graphics card. As an application we validate Gasser's results that Nine-Men-Morris is a draw on a personal computer. Moreover, our solution is strong, while for the opening phase Gasser only provided a weak solution.

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.

For general two-player turn-taking games, first solvers have been contributed. Algorithms for multi-player games like Maxn, however, cannot classify general games robustly, and its extension Soft-Maxn, which can play optimally against unknown and weak opponents, demands large amounts of memory. As RAM is a scarce resource, this paper proposes a memory-efficient implementation of the Soft-Maxnalgorithm, by exploiting the functional representation of state and evaluation sets with BDDs.

Solid state disks based on flash memory are an apparent alternative to hard disks for external memory search. Random reads are much faster, while random writes are generally not. In this paper, we illustrate how this influences the time-space trade-offs for scaling semi-external LTL model checking algorithms that request a constant number of bits per state in internal, and full state vectors on external memory. We invent a complexity model to analyze the effect of outsourcing the perfect hash function from random access to flash memory. In this model a 1-bit semi-external I/O efficient LTL model checking algorithm is proposed that generates minimal counterexamples.

In a field of research about general reasoning mechanisms, it is essential to have appropriate benchmarks. Ideally, the benchmarks should reflect possible applications of the developed technology. In AI Planning, researchers more and more tend to draw their testing examples from the benchmark collections used in the International Planning Competition (IPC). In the organization of (the deterministic part of) the fourth IPC, IPC-4, the authors therefore invested significant effort to create a useful set of benchmarks. They come from five different (potential) real-world applications of planning: airport ground traffic control, oil derivative transportation in pipeline networks, model-checking safety properties, power supply restoration, and UMTS call setup. Adapting and preparing such an application for use as a benchmark in the IPC involves, at the time, inevitable (often drastic) simplifications, as well as careful choice between, and engineering of, domain encodings. For the first time in the IPC, we used compilations to formulate complex domain features in simple languages such as STRIPS, rather than just dropping the more interesting problem constraints in the simpler language subsets. The article explains and discusses the five application domains and their adaptation to form the PDDL test suites used in IPC-4. We summarize known theoretical results on structural properties of the domains, regarding their computational complexity and provable properties of their topology under the h+ function (an idealized version of the relaxed plan heuristic). We present new (empirical) results illuminating properties such as the quality of the most wide-spread heuristic functions (planning graph, serial planning graph, and relaxed plan), the growth of propositional representations over instance size, and the number of actions available to achieve each fact; we discuss these data in conjunction with the best results achieved by the different kinds of planners participating in IPC-4.

We provide an overview of the organization and results of the deterministic part of the 4th International Planning Competition, i.e., of the part concerned with evaluating systems doing deterministic planning. IPC-4 attracted even more competing systems than its already large predecessors, and the competition event was revised in several important respects. After giving an introduction to the IPC, we briefly explain the main differences between the deterministic part of IPC-4 and its predecessors. We then introduce formally the language used, called PDDL2.2 that extends PDDL2.1 by derived predicates and timed initial literals. We list the competing systems and overview the results of the competition. The entire set of data is far too large to be presented in full. We provide a detailed summary; the complete data is available in an online appendix. We explain how we awarded the competition prizes.

This paper provides a novel approach for optimal route planning by making efficient use of the underlying geometrical structure. It combines classical artificial intelligence exploration with computational geometry. Given a set of global positioning system (GPS) trajectories, the input is refined by geometric filtering and rounding algorithms. For constructing the graph and the according point-localization structure, fast scan line and divide-and-conquer algorithms are applied. For speeding up the optimal online search algorithms, the geometrical structure of the inferred weighted graph is exploited in two ways; it is compressed while retaining the original information for unfolding resulting shortest paths and is then annotated by lower bounds and refined topographic information (for example, by the bounding boxes of all shortest paths that start with a given edge). Traffic disturbances can result in an increase in travel time for the affected area that, in turn, can affect the precomputed information. This paper discusses two models of introducing dynamics in a navigation system. The online planning system GPS-ROUTE implements the above techniques and provides a client-server web interface to answer a series of shortest-path or shortest-time queries.

The Model Checking Integrated Planning System (MIPS) is a temporal least commitment heuristic search planner based on a flexible object-oriented workbench architecture. Its design clearly separates explicit and symbolic directed exploration algorithms from the set of on-line and off-line computed estimates and associated data structures. MIPS has shown distinguished performance in the last two international planning competitions. In the last event the description language was extended from pure propositional planning to include numerical state variables, action durations, and plan quality objective functions. Plans were no longer sequences of actions but time-stamped schedules. As a participant of the fully automated track of the competition, MIPS has proven to be a general system; in each track and every benchmark domain it efficiently computed plans of remarkable quality. This article introduces and analyzes the most important algorithmic novelties that were necessary to tackle the new layers of expressiveness in the benchmark problems and to achieve a high level of performance. The extensions include critical path analysis of sequentially generated plans to generate corresponding optimal parallel plans. The linear time algorithm to compute the parallel plan bypasses known NP hardness results for partial ordering by scheduling plans with respect to the set of actions and the imposed precedence relations. The efficiency of this algorithm also allows us to improve the exploration guidance: for each encountered planning state the corresponding approximate sequential plan is scheduled. One major strength of MIPS is its static analysis phase that grounds and simplifies parameterized predicates, functions and operators, that infers knowledge to minimize the state description length, and that detects domain object symmetries. The latter aspect is analyzed in detail. MIPS has been developed to serve as a complete and optimal state space planner, with admissible estimates, exploration engines and branching cuts. In the competition version, however, certain performance compromises had to be made, including floating point arithmetic, weighted heuristic search exploration according to an inadmissible estimate and parameterized optimization.