A Framework for the Secretary Problem on the Intersection of Matroids

The secretary problem became one of the most prominent online selection problems due to its numerous applications in online mechanism design. The task is to select a maximum weight subset of elements subject to given constraints, where elements arrive one-by-one in random order, revealing a weight upon arrival. The decision whether to select an element has to be taken immediately after its arrival. The different applications that map to the secretary problem ask for different constraint families to be handled. The most prominent ones are matroid constraints, which both capture many relevant settings and admit strongly competitive secretary algorithms. However, dealing with more involved constraints proved to be much more difficult, and strong algorithms are known only for a few specific settings. In this paper, we present a general framework for dealing with the secretary problem over the intersection of several matroids. This framework allows us to combine and exploit the large set of matroid secretary algorithms known in the literature. As one consequence, we get constant-competitive secretary algorithms over the intersection of any constant number of matroids whose corresponding (single-)matroid secretary problems are currently known to have a constant-competitive algorithm. Moreover, we show that our results extend to submodular objectives.

Rigid body dynamics simulation for robot motion planning

Alan Ettlin

The development of robot motion planning algorithms is inherently a challenging task. This is more than ever true when the latest trends in motion planning are considered. Some motion planners can deal with kinematic and dynamic constraints induced by the mechanical structure of the robot. Another class of motion planners fulfill various types of optimality conditions, yet others include means of dealing with uncertainty about the robot and its environment. Sensor-based motion planners gather information typically afflicted with errors about a partially known environment in order to plan a trajectory therein. In another research area it is investigated how multiple robots best cooperate to solve a common task. In order to deal with the complexity of developing motion planning algorithms, it is proposed in this document to resort to a simulation environment. The advantages of doing so are outlined and a system named Ibex presented which is well suited to support motion planner development. The developed framework makes use of rigid body dynamics algorithms as simulation kernel. Further, various components are included which integrate the simulation into existing engineering environments. Simulation content can be conveniently developed through extensions of well-established 3D modelling tools. The co-simulation with components from other domains of physics is provided by the integration into a leading dynamic modelling environment. Robotic actuator models can be combined with a rigid body dynamics simulation using this mechanism. The same configuration also allows to conveniently develop control algorithms for a rigid body dynamics setup and offers powerful tools for handling and analysing simulation data. The developed simulation framework also offers physics-based models for simulating various sensors, most prominently a model for sensor types based on wave propagation, such as laser range finding devices. Application examples of the simulation framework are presented from the mobile robotics rough-terrain motion planning domain. Three novel rough-terrain planning algorithms are presented which are extensions of known approaches. To quantify the navigational difficulty on rough terrain, a new generic measure named "obstacleness" is proposed which forms the basis of the proposed algorithms. The first algorithm is based on Randomised Potential Field Planners (RPP) and consequently is a local algorithm. The second proposed planner extends RRTconnect , a bi-directional Rapidly Exploring Random Tree (RRT) algorithm and biases exploration of the search space towards easily traversable regions. The third planner is an extension of the second approach and uses the same heuristic to grow a series of additional local RRTs. This allows it to plan trajectories through complex distributions of navigational difficulty benefitting from easy regions throughout the motion plan. A complete example is shown in which the proposed algorithms form the basis for sensor-based dynamic re-planning simulated in the presented framework. In the scenario, a simulated planetary rover navigates a long distance over rough terrain while gathering sensor data about the terrain topography. Where obstacles are sensed which interfere with the original motion plan, dynamic re-planning routines are applied to circumnavigate the hindrances. In the course of this document a complete simulation environment is presented by means of a theoretical background and application examples which can significantly support the development of robot motion planning algorithms. The framework is capable of simulating setups which fulfil the requirements posed by stateof-the-art motion planning algorithm development.

EPFL2006

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Moran Feldman, Ola Nils Anders Svensson, Rico Zenklusen

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call online contention resolution schemes (OCRSs), is applicable to many online selection problems, including Bayesian online selection, oblivious posted pricing mechanisms, and stochastic probing models. It allows for handling a wide set of constraints and shares many strong properties of offline contention resolution schemes. In particular, OCRSs for different constraint families can be combined to obtain an OCRS for their intersection. Moreover, we can approximately maximize submodular functions in the online settings we consider. We thus get a broadly applicable framework for several online selection problems, which improves on previous approaches in terms of the types of constraints that can be handled, the objective functions that can be dealt with, and the assumptions on the strength of the adversary. Furthermore, we resolve two open problems from the literature; namely, we present the first constant-factor constrained oblivious posted price mechanism for matroid constraints and the first constant-factor algorithm for weighted stochastic probing with deadlines.

2021

Rigid body dynamics simulation for robot motion planning

Alan Ettlin

EPFL2006