While motion planning approaches for automated driving often focus on safety and mathematical optimality with respect to technical parameters, they barely consider convenience, perceived safety for the passenger and comprehensibility for other traffic participants. For automated driving in mixed traffic, however, this is key to reach public acceptance. In this paper, we revise the problem statement of motion planning in mixed traffic: Instead of largely simplifying the motion planning problem to a convex optimization problem, we keep a more complex probabilistic multi agent model and strive for a near optimal solution. We assume cooperation of other traffic participants, yet being aware of violations of this assumption. This approach yields solutions that are provably safe in all situations, and convenient and comprehensible in situations that are also unambiguous for humans. Thus, it outperforms existing approaches in mixed traffic scenarios, as we show in our simulation environment.
The optimal solution @math thus can be found via the minimization of this integral: This approach has for example been applied by and has proven to work for a large variety of scenarios @cite_14 , @cite_0 . However, as described by the authors, the trajectories were rather defensive and sometimes close to the one of human learners taking driving lessons. This behavior can be explained mainly by the impact of the unknown evolution of the scene @math that depends on the own action @math , respectively @math . Further, the uncertain perception of the status quo @math was dealt with by using security margins.
@cite_0 @cite_14
2055501135 2604884452 1971467559 2473549844
This paper presents a generic approach for tactical decision-making under uncertainty in the context of driving. The complexity of this task mainly stems from the fact that rational decision-making in this context must consider several sources of uncertainty: The temporal evolution of situations cannot be predicted without uncertainty because other road users behave stochastically and their goals and plans cannot be measured. Even more important, road users are only able to perceive a tiny part of the current situation with their sensors because measurements are noisy and most of the environment is occluded. In order to anticipate the consequences of decisions a probabilistic approach, considering both forms of uncertainty, is necessary. The authors address this by formulating the task of driving as a continuous Partially Observable Markov Decision Process (POMDP) that can be automatically optimized for different scenarios. As driving is a continuous-space problem, the belief space is infinite-dimensional. The authors do not use a symbolic representation or discretize the state space a priori because there is no representation of the state space that is optimal for every situation. Instead, they employ a continuous POMDP solver that learns a good representation of the specific situation. We consider the problem of provably optimal exploration in reinforcement learning for finite horizon MDPs. We show that an optimistic modification to value iteration achieves a regret bound of @math where @math is the time horizon, @math the number of states, @math the number of actions and @math the number of time-steps. This result improves over the best previous known bound @math achieved by the UCRL2 algorithm of , 2010. The key significance of our new results is that when @math and @math , it leads to a regret of @math that matches the established lower bound of @math up to a logarithmic factor. Our analysis contains two key insights. We use careful application of concentration inequalities to the optimal value function as a whole, rather than to the transitions probabilities (to improve scaling in @math ), and we define Bernstein-based "exploration bonuses" that use the empirical variance of the estimated values at the next states (to improve scaling in @math ). Two players A and B are randomly placed on a line. The distribution of the distance between them is unknown except that the expected initial distance of the (two) players does not exceed some constant @math The players can move with maximal velocity 1 and would like to meet one another as soon as possible. Most of the paper deals with the asymmetric rendezvous in which each player can use a different trajectory. We find rendezvous trajectories which are efficient against all probability distributions in the above class. (It turns out that our trajectories do not depend on the value of @math ) We also obtain the minimax trajectory of player A if player B just waits for him. This trajectory oscillates with a geometrically increasing amplitude. It guarantees an expected meeting time not exceeding @math We show that, if player B also moves, then the expected meeting time can be reduced to @math The expected meeting time can be further reduced if the players use mixed strategies. We show that if player B rests, then the optimal strategy of player A is a mixture of geometric trajectories. It guarantees an expected meeting time not exceeding @math This value can be reduced even more (below @math ) if player B also moves according to a (correlated) mixed strategy. We also obtain a bound for the expected meeting time of the corresponding symmetric rendezvous problem. We consider the adversarial convex bandit problem and we build the first @math -time algorithm with @math -regret for this problem. To do so we introduce three new ideas in the derivative-free optimization literature: (i) kernel methods, (ii) a generalization of Bernoulli convolutions, and (iii) a new annealing schedule for exponential weights (with increasing learning rate). The basic version of our algorithm achieves @math -regret, and we show that a simple variant of this algorithm can be run in @math -time per step at the cost of an additional @math factor in the regret. These results improve upon the @math -regret and @math -time result of the first two authors, and the @math -regret and @math -time result of Hazan and Li. Furthermore we conjecture that another variant of the algorithm could achieve @math -regret, and moreover that this regret is unimprovable (the current best lower bound being @math and it is achieved with linear functions). For the simpler situation of zeroth order stochastic convex optimization this corresponds to the conjecture that the optimal query complexity is of order @math .