Dr. Stefan Edelkamp

This book is concerned with Algorithmic Intelligence. While an algorithm can hardly be judged to be intelligent on its own, the basis of what is attributed to computer intelligence is of algorithmic roots. There is little doubt that the smaller the space consumption of an algorithm and the faster the access to its data structures are, the better the inferences.

This work presents a four-stage framework that solves a capacitated multi-robot task-motion planning problem with time windows using a location-routing task motion planning (LRTMP) approach that respects the vehicles' maximum item load. We begin by first generating collision-free regions of interest using a probabilistic roadmap. Secondly, we use capacitated clustering algorithms to determine how many facilities to open based on the vehicle's maximum item load and proximity of the goal regions. For each cluster, we also determine the location of the facility. In the third stage, we deploy our task allocation algorithm to determine which vehicle should visit which cluster. Finally, we use an off-the-shelf domain-independent planner and a second-order vehicle model in an obstacle-rich environment for our simulated experiments. We compare the performance of our LRTMP solution with the related work. Results measure the runtime, the number of goods collected, and the average travel distance.

This work presents a solution to the electric location-routing problem with capacitated energy and item load using a location-routing task motion planning approach. Our solution consists of three stages, (i) we start by generating collision-free regions of interest using a probabilistic roadmap. (ii) we propose modifications to the capacitated hierarchical agglomerative clustering algorithm (CAC). First, we consider the vehicle's starting location, ensuring that the vehicle has enough energy to enter a cluster and visit all the customers in the cluster with a full battery charge. Secondly, an adaptive threshold approach ensures the vehicle can traverse between the clusters and visit the customers. This stage generates capacitated clusters within the vehicle's capacity and decides how many facilities to open and their locations to satisfy the customers' demands. (iii) we use an off-the-shelf PDDL solver and a second-order vehicle model in an obstacle-rich environment. We compare the performance of our approach to CAC. For our simulated experiments, we analyze various routes and costs for different attributes, such as the cluster strategies, energy capacity, number of customers and item load, where the results measure the runtime, number of customer visits and the average travel distance. When the vehicle cannot visit all the customers in a cluster due to a limited energy capacity, it seeks to maximize the number of customer visits.

Learning a well-informed heuristic function for hard planning domains is an elusive problem. Although there are known neural network architectures to represent such heuristic knowledge, it is not obvious what concrete information is learned and whether techniques aimed at understanding the structure help in improving the quality of the heuristics. This paper presents a network model that learns a heuristic function capable of relating distant parts of the state space via optimal plan imitation using the attention mechanism which drastically improves the learning of a good heuristic function. The learning of this heuristic function is further improved by the use of curriculum learning, where newly solved problem instances are added to the training set, which, in turn, helps to solve problems of higher complexities and train from harder problem instances. The methodologies used in this paper far exceed the performances of all existing baselines including known deep learning approaches and classical planning heuristics. We demonstrate its effectiveness and success on grid-type PDDL domains, namely Sokoban, maze-with-teleports and sliding tile puzzles.

Skat is a strategy-rich card game, posing several combinatorial questions to advanced computer play for improved cooperation and competition. In this paper we advance trick-taking play by introducing hope cards, namely cards that excel not in all, but in the set of winnable worlds. Besides winning rate and scoring, we evaluate the strength of computer engine mainly based on the proximity of its results to the outcome of the open-card solver. This way, the opponents’ and the overall playing strength of a state-of-the-art automated Skat player has been upgraded significantly, while keeping the response time small for swift play. For the first time, we won an online tournament with 20 series against a top German Skat player.

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 decision making while competing for limited resources in adversarial environments is important for many real-world applications (e.g. two Taxi companies competing for customers). Decision-making techniques such as Automated planning have to take into account possible actions of adversary (or competing) agents. That said, the agent should know what the competitor will likely do and then generate its plan accordingly. In this paper we propose a novel approach for estimating strategies of the adversary (or the competitor), sampling its actions that might hinder agent's goals by interfering with the agent's actions. The estimated competitor strategies are used in plan generation such that agent's actions have to be applied prior to the ones of the competitor, whose estimated times dictate the deadlines. We empirically evaluate our approach leveraging sampling of competitor's actions by comparing it to the naive approach optimizing the make-span (not taking the competing agent into account at all) and to Nash Equilibrium (mixed) strategies.

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.

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.

This paper shows that domain-independent tools from classical planning can be used to model and solve a broad class of game-theoretic problems we call Cost-Adversarial Planning Games (CAPGs). We define CAPGs as 2-player normal-form games specified by a planning task and a finite collection of cost functions. The first player (a planning agent) strives to solve a planning task optimally but has limited knowledge about its action costs. The second player (an adversary agent) controls the actual action costs. Even though CAPGs need not be zero-sum, every CAPG has an associated zero-sum game whose Nash equilibrium provides the optimal randomized strategy for the planning agent in the original CAPG. We show how to find the Nash equilibrium of the associated zero-sum game using a cost-optimal planner via the Double Oracle algorithm. To demonstrate the expressivity of CAPGs, we formalize a patrolling security game and several IPC domains as CAPGs.

Effective plan generation in adversarial environments has totake 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 estimatingstrategies of the adversary, sampling actions that interferewith the agent’s ones. The estimated competitor strategies areused in plan generation by considering that agent’s actionshave to be applied prior to the ones of the competitor, whoseestimated times dictate the agent’s deadlines. Missing thesedeadlines entails additional plan cost