Maximilian Graf

Maximilian Graf, Victor Thuot

We study multiple change point localization under bandit feedback. An unknown piecewise-constant function on a compact interval can be queried sequentially at adaptively chosen inputs, and each query returns a noisy evaluation of the function. The goal is to identify a prescribed number of discontinuities, known as change points, within a target precision $η$ and confidence level $1-δ$, while using as few samples as possible. We propose an adaptive algorithm that first detects intervals likely to contain change points and then refines their locations to precision $η$. We establish non-asymptotic upper bounds on its sample budget, together with corresponding lower bounds. Prior work shows that jump magnitudes alone determine the asymptotic sample complexity as $δ\to 0$. We reveal that this picture is incomplete beyond this regime. We demonstrate, both empirically and theoretically, that for general $δ$ and $η$, the complexity is jointly governed by the jumps and the relative positions of the change points.

Maximilian Graf, Alexandra Carpentier, Nicolas Verzelen

Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that both the experts and the questions can be ordered, namely that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. When $n=d$, this also encompasses the strongly stochastic transitive (SST) model from the tournament literature. Here, we focus on the relevant problem of deciphering small entries of $M$ from large entries of $M$, which is key in crowdsourcing for efficient allocation of workers to questions. More precisely, we aim at recovering a (or several) level set $p$ of the matrix up to a precision $h$, namely recovering resp. the sets of positions $(i,j)$ in $M$ such that $M_{ij}>p+h$ and $M_{i,j}<p-h$. We consider, as a loss measure, the number of misclassified entries. As our main result, we construct an efficient polynomial-time algorithm that turns out to be minimax optimal for this classification problem. This heavily contrasts with existing literature in the SST model where, for the stronger reconstruction loss, statistical-computational gaps have been conjectured. More generally, this shades light on the nature of statistical-computational gaps for permutations models.

Maximilian Graf, Victor Thuot, Nicolas Verzelen

We study the problem of clustering a set of items based on bandit feedback. Each of the $n$ items is characterized by a feature vector, with a possibly large dimension $d$. The items are partitioned into two unknown groups such that items within the same group share the same feature vector. We consider a sequential and adaptive setting in which, at each round, the learner selects one item and one feature, then observes a noisy evaluation of the item's feature. The learner's objective is to recover the correct partition of the items, while keeping the number of observations as small as possible. We provide an algorithm which relies on finding a relevant feature for the clustering task, leveraging the Sequential Halving algorithm. With probability at least $1-δ$, we obtain an accurate recovery of the partition and derive an upper bound on the budget required. Furthermore, we derive an instance-dependent lower bound, which is tight in some relevant cases.

Maximilian Graf, Oliver Speidel, Jona Ruof et al.

The Institute of Measurement, Control and Microtechnology at Ulm University investigates advanced driver assistance systems for decades and concentrates in large parts on autonomous driving. It is well known that motion planning is a key technology for autonomous driving. It is first and foremost responsible for the safety of the vehicle passengers as well as of all surrounding traffic participants. However, a further task consists in providing a smooth and comfortable driving behavior. In Ulm, we have the grateful opportunity to test our algorithms under real conditions in public traffic and diversified scenarios. In this paper, we would like to give the readers an insight of our work, about the vehicle, the test track, as well as of the related problems, challenges and solutions. Therefore, we will describe the motion planning system and explain the implemented functionalities. Furthermore, we will show how our vehicle moves through public road traffic and how it deals with challenging scenarios like e.g. driving through roundabouts and intersections.

Oliver Speidel, Maximilian Graf, Ankit Kaushik et al.

Efficient trajectory planning for urban intersections is currently one of the most challenging tasks for an Autonomous Vehicle (AV). Courteous behavior towards other traffic participants, the AV's comfort and its progression in the environment are the key aspects that determine the performance of trajectory planning algorithms. To capture these aspects, we propose a novel trajectory planning framework that ensures social compliance and simultaneously optimizes the AV's comfort subject to kinematic constraints. The framework combines a local continuous optimization approach and an efficient driver model to ensure fast behavior prediction, maneuver generation and decision making over long horizons. The proposed framework is evaluated in different scenarios to demonstrate its capabilities in terms of the resulting trajectories and runtime.

Oliver Speidel, Maximilian Graf, Thanh Phan-Huu et al.

Efficient behavior and trajectory planning is one of the major challenges for automated driving. Especially intersection scenarios are very demanding due to their complexity arising from the variety of maneuver possibilities and other traffic participants. A key challenge is to generate behaviors which optimize the comfort and progress of the ego vehicle but at the same time are not too aggressive towards other traffic participants. In order to maintain real time capability for courteous behavior and trajectory planning, an efficient formulation of the optimal control problem and corresponding solving algorithms are required. Consequently, a novel planning framework is presented which considers comfort and progress as well as the courtesy of actions in a graph-based behavior planning module. Utilizing the low level trajectory generation, the behavior result can be further optimized for driving comfort while satisfying constraints over the whole planning horizon. According experiments show the practicability and real time capability of the framework.