Dr. Stefan Edelkamp

There is a huge industrial interest in highly capable recommender systems (RS) as key revenue drivers in smaller-sized web shops for SMEs to larger companies like Amazons. Besides matrix factorization one of the core solution methods for collaborative and content-based filtering are clustering algorithms with multi-dimensional sparse matrices, which are often hit by the curse of dimensionality. In classification, binarization and fractals have been shown a effective method providing better scalability and to allow for faster compuation. In this dissertation we extend the findings to clustering and apply it to artificial and industrial cases for recommendation. As one of the most successful machine learning applications in place, RS also facilitates an important technique to handle information overload. It’s hypothesised that, if a person’s preferences are known, RS can also recommend products that the person may like. RS can help to make a decision on a variety of items, such as movies, books, and restaurants. Content-based and collaborative filtering are commonly used to make those recommendations. However, there are two more options: demographic and hybrid filtering. Each system has several advantages for the customer and the company.

Whereas automated planning is appropriate for aiming at longer-term goals, (deep) reinforcement learning is appropriate for aiming at shorter-term goals or rewards. Effective combination of these techniques can improve decision making in dynamic environments such that planning can guide the agent towards its goals while reinforcement learning can help the agent to stay safe.

One central showcase in Artificial Intelligence is to illustrate that computers can beat humans in games. While, on the first glance, mastering games itself might be less attractive for people not interested in playing, visible success stories in playing games have shown to be influential for AI research in general. As many fully observable games have either been solved or AIs show superhuman performance, the next AI challenge are games with randomness and incomplete information due to parts of the state being hidden. Skat is a fascinating combinatorial card game, show-casing many of the intrinsic challenges for modern AI systems such as cooperative and adversarial behaviors (among the players), randomness (in the deal), and partial knowledge (due to hidden cards). Given the larger number of tricks and higher degree of uncertainty, reinforcement learning is less effective compared to classical board games like Chess and Go. While there is impressive research on playing non-cooperative card games like Poker, for multi- player trick-taking games, according to expert wisdom, human play is still superior to computer play. In this PhD we develop an automated card game player able to beat even best human players. With three players and 32 cards Skat is more concise than Bridge, and still full of virtue. From a combinatorial search perspective, Skat has more than 2.8 quadrillion possible deals. The probability that two deals appear twice of at least 50% yields more than 40 million games to be played, easily covering the lifetime of a player. The bidding and the game selection stages use statistical knowledge of winning ratios in expert games, stored in tables and addressed via patterns of winning features resulting in a predictor W(h) for hand h with high accuracy. The inferred probabilities are then exploited in the first three stages of the Skat game: bidding, skat taking and game selection, and skat putting. For each bidding value and each game type selected it generates and filters all 231 skats and takes the average of the expected payoff of skat putting, determined as the maximum of the 66 skats to be put. For null games, we estimate the winning probability W(h,c) in each suit c. For all other games, it considers a hash table addressed by the winning parameters. Statistical tests showed that these parameters are essential attributes to accurately assess the probability of winning a trump game. In particular, a grand table is built on top of seven of these winning parameters and the suit table uses nine of them. Trick-taking is arranged according to an ensemble of different card recommendations.

Sampling-based motion planning has seen tremendous improvements in terms of scalability and expressiveness. However, the integration of task and motion planning still poses several open challenges. Consider for example the scenario, where a team of robots must coordinate their movements and their task allocations to complete a mission as soon as possible such as in the DARPA Subterranean Challenge. Different tasks have different durations and resource consumption, and each task must be performed within one of the available time windows. Such a challenging scenario requires temporal reasoning in addition to finding the best path between task locations. This project aims to address these challenges by combining sampling-based motion planning with temporal task planning. With the technology developed in the project we will be able to efficiently generate and execute plans for long-term tasks of several moving robots in rough environments with obstacles, fast enough even for real-time simulations. The robots, the environment model and the planning task specification can be adapted non-intrusively, essential for solution prototypes in many applications from surveillance with drones, via Logistics applications to household service robotics. Multi-Goal Task-Motion Planning touches many involved research questions, e.g., handling the dynamics of the robot, avoiding existing obstacles, visiting multiple waypoints, performing tasks, all this while dealing with time windows, deadlines, and resource constraints. For a robot in a real-world environment there are frequent task requests like visiting goals (in the best possible order) to minimize travel time for inspecting an object, before considering another. These temporal requests are attached to the physical world and must be reflected in the motion planning of the robot. For complex operations on a robot, the reachability of one goal via path planning is not enough, as many goals in form of waypoints must be visited for completing a plan. Moreover, robots have tasks to perform at each waypoint, that take time and require resources. While there are automata-based solutions for finding plans for several goals, by the exponential growth in the automata representation, they do not scale well. Engineered solutions offer better results as the performance of our prototype system shows. Ever since there have been an attempt to solve the integrated task and motion planning problem for complex robots. This project joins sampling-based motion planning with guidance, established by heuristics that are found through problem abstractions. The challenge is to combine the exploration in the continuous space of valid trajectories, imposed by the dynamics of the robot’s nonlinear, non-holomorphic, and hybrid system specification, and the discrete space that is associated with the task planning. While there is an alternative to include motion planning modules in the preconditions of an action, our contribution is iterating a loop of solving the abstraction to guide the expansion of the sampling-based motion tree to generate valid trajectories.

With Quicksort contributed by Tony Hoare about 60 years ago, the sorting problem was essentially be solved. From a practical point of view it showed that the name was correctly chosen, and with an average case in O(n lg n) the theoretical performance was good. However, there are new ideas around that have given some more insights: Worst-Case Stoppers like Heapsort in Introsort by David Musser as in the C++ STL, and Multi-Pivots by Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch as in Java’s library implementation are established. We contributed BlockQuicksort, about twice as fast than Introsort, minimizing the number of branch mispredictions, as well as QuickMerge- and QuickXSort - new hybrids showning outstanding theoretical performance. There have also be efforts in accelerating the base cases to improve on Insertionsort and Merge-Insertion. and towards proper parallelizations. In the project we will explore the extremes and middle grounds of sequential sorting routine, e.g., whether an implementation of a lower bound + o(n) quick sorting algorithm with O(n lg n) work is possible.

Heuristic search is a powerful approach to solve complex planning problems in AI applications. Research has so far mainly focused on sequential methods, which cannot gain the full benefits ofparallelism of modern system architectures with multi- and many-core CPUs, workstation clusters and parallel high-performance computers. As many heuristic search algorithms are guided by memory tables, fast parallel data access to different memory layers (caches, HBM, DRAM) is important for the overall efficiency. In this project we consider different approaches to implement distributed versions of heuristic search algorithms like A* and IDA*. We interpret distributed search when more than one search process isinvoked, which can be due to partitioning the workload among different processors. Apart from work-load distribution, the most important challenge in distributed processing is to keep the communication overhead between the different search processes at an acceptable level (e.g. linear of logarithmic to the number of threads or processes). Modern computers can exploit parallelism at various hardware levels. In parallel search the node exploration (generating the successors, computing the heuristic estimates, etc.) can be distributed among different threads or processes; be it workstation clusters or parallel and multi-core processor environments. Parallel heuristic search can either be synchronous and asynchronous, a notation which refers tothe exchange of exploration information (nodes to expand, duplicates to eliminate) among different (depth-first) search processes. We consider algorithmic refinements like transposition-driven scheduling. Early parallel formulations of A* assume that the graph is a tree, so that there is no needto keep a Closed list of visited nodes to avoid duplicates. If the graph is not a tree, most frequently, static hash functions distribute the workload. We identify differences in shared memory designs (e.g.multi-core processors) and distributed memory architectures (e.g. workstation clusters). Newer parallel implementations of A* include frontier search and the use of large amounts of external memory. The design of effective data structures for concurrent access especially for the search frontier is essential. One distributed data structure that is introduced features both the capabilities of heaps and binary search trees. In parallel external search we consider how to integrate external and distributed search.The straight-forward approach of a massively parallel breadth-first search using a map-reduce based deduplication scheme generates a vast amount of communication to deduplicate the search front, which limits the scalability of the approach. Due to a high memory demand, the approach also encounters limitations especially in the solution of very difficult problems - for which parallel parallel search is particularly important. It seems that methods based on depth-first search offer more flexibility with a good potential for improvement, especially when it comes to utilizing parallel hardware.