4 Search Results for "Stiller, Christoph"


Document
Fast Robust Shortest Path Computations

Authors: Christoph Hansknecht, Alexander Richter, and Sebastian Stiller

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)


Abstract
We develop a fast method to compute an optimal robust shortest path in large networks like road networks, a fundamental problem in traffic and logistics under uncertainty. In the robust shortest path problem we are given an s-t-graph D(V,A) and for each arc a nominal length c(a) and a maximal increase d(a) of its length. We consider all scenarios in which for the increased lengths c(a) + bar{d}(a) we have bar{d}(a) <= d(a) and sum_{a in A} (bar{d}(a)/d(a)) <= Gamma. Each path is measured by the length in its worst-case scenario. A classic result [Bertsimas and Sim, 2003] minimizes this path length by solving (|A| + 1)-many shortest path problems. Easily, (|A| + 1) can be replaced by |Theta|, where Theta is the set of all different values d(a) and 0. Still, the approach remains impractical for large graphs. Using the monotonicity of a part of the objective we devise a Divide and Conquer method to evaluate significantly fewer values of Theta. This methods generalizes to binary linear robust problems. Specifically for shortest paths we derive a lower bound to speed-up the Divide and Conquer of Theta. The bound is based on carefully using previous shortest path computations. We combine the approach with non-preprocessing based acceleration techniques for Dijkstra adapted to the robust case. In a computational study we document the value of different accelerations tried in the algorithm engineering process. We also give an approximation scheme for the robust shortest path problem which computes a (1 + epsilon)-approximate solution requiring O(log(d^ / (1 + epsilon))) computations of the nominal problem where d^ := max d(A) / min (d(A)\{0}).

Cite as

Christoph Hansknecht, Alexander Richter, and Sebastian Stiller. Fast Robust Shortest Path Computations. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{hansknecht_et_al:OASIcs.ATMOS.2018.5,
  author =	{Hansknecht, Christoph and Richter, Alexander and Stiller, Sebastian},
  title =	{{Fast Robust Shortest Path Computations}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{5:1--5:21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.5},
  URN =		{urn:nbn:de:0030-drops-97100},
  doi =		{10.4230/OASIcs.ATMOS.2018.5},
  annote =	{Keywords: Graph Algorithms, Shortest Paths, Robust Optimization}
}
Document
10371 Abstracts Collection – Dynamic Maps

Authors: Claus Brenner, Wolfram Burgard, Marc Pollefeys, and Christoph Stiller

Published in: Dagstuhl Seminar Proceedings, Volume 10371, Dynamic Maps (2011)


Abstract
From September 12th to 17th, 2010, the Dagstuhl Seminar 10371 ``Dynamic Maps '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Claus Brenner, Wolfram Burgard, Marc Pollefeys, and Christoph Stiller. 10371 Abstracts Collection – Dynamic Maps. In Dynamic Maps. Dagstuhl Seminar Proceedings, Volume 10371, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{brenner_et_al:DagSemProc.10371.1,
  author =	{Brenner, Claus and Burgard, Wolfram and Pollefeys, Marc and Stiller, Christoph},
  title =	{{10371 Abstracts Collection – Dynamic Maps}},
  booktitle =	{Dynamic Maps},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10371},
  editor =	{Claus Brenner and Wolfram Burgard and Marc Pollefeys and Christoph Stiller},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10371.1},
  URN =		{urn:nbn:de:0030-drops-29526},
  doi =		{10.4230/DagSemProc.10371.1},
  annote =	{Keywords: Dynamic maps, computer vision, photogrammetry, robotics, computer graphics, geoinformatics, driver assistance}
}
Document
10371 Executive Summary – Dynamic Maps

Authors: Claus Brenner, Wolfram Burgard, Marc Pollefeys, and Christoph Stiller

Published in: Dagstuhl Seminar Proceedings, Volume 10371, Dynamic Maps (2011)


Abstract
In recent years, the advent of car navigation systems has laid the ground for an entirely new industry sector, consisting of map producers, car/ personal/ smart phone navigation manufacturers, and service providers. It has probably gone unnoticed that navigation systems mark a major change in the way we use maps. Partially, they are still just a replacement for traditional maps, providing a means to store and visualize a representation of the environment. In contrast to the traditional use of maps, however, navigation systems perform computations using the map's data structures, such as shortest route, map matching, and route guidance. That is, from an abstract point of view, part of the map is made for machine use only – the user has no direct access to it but rather is only presented the outcome of the computations.

Cite as

Claus Brenner, Wolfram Burgard, Marc Pollefeys, and Christoph Stiller. 10371 Executive Summary – Dynamic Maps. In Dynamic Maps. Dagstuhl Seminar Proceedings, Volume 10371, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{brenner_et_al:DagSemProc.10371.2,
  author =	{Brenner, Claus and Burgard, Wolfram and Pollefeys, Marc and Stiller, Christoph},
  title =	{{10371 Executive Summary – Dynamic Maps}},
  booktitle =	{Dynamic Maps},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10371},
  editor =	{Claus Brenner and Wolfram Burgard and Marc Pollefeys and Christoph Stiller},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10371.2},
  URN =		{urn:nbn:de:0030-drops-29512},
  doi =		{10.4230/DagSemProc.10371.2},
  annote =	{Keywords: Dynamic maps, spatial data infrastructure, SLAM, map matching, autonomous navigation, spatial cognition, data fusion, information retrieval, intelligent vehicles, 3D scene perception, scene understanding, 3D reconstruction}
}
Document
Real-Time Monocular Visual Odometry for On-Road Vehicles with 1-Point RANSAC

Authors: Davide Scaramuzza, Friedrich Fraundorfer, and Roland Siegwart

Published in: Dagstuhl Seminar Proceedings, Volume 10371, Dynamic Maps (2011)


Abstract
The first biggest problem in visual motion estimation is data association; matched points contain many outliers that must be detected and removed for the motion to be accurately estimated. In the last few years, a very established method for removing outliers has been the "5-point RANSAC" algorithm which needs a minimum of 5 point correspondences to estimate the model hypotheses. Because of this, however, it can require up to thousand iterations to find a set of points free of outliers. In this talk, I will show that by exploiting the non-holonomic constraints of wheeled vehicles (e.g. cars, bikes, mobile robots) it is possible to use a restrictive motion model which allows us to parameterize the motion with only 1 point correspondence. Using a single feature correspondence for motion estimation is the lowest model parameterization possible and results in the most efficient algorithm for removing outliers: 1-point RANSAC. The second problem in monocular visual odometry is the estimation of the absolute scale. I will show that vehicle non-holonomic constraints make it also possible to estimate the absolute scale completely automatically whenever the vehicle turns. In this talk, I will give a mathematical derivation and provide experimental results on both simulated and real data over a large image dataset collected during a 25 Km path.

Cite as

Davide Scaramuzza, Friedrich Fraundorfer, and Roland Siegwart. Real-Time Monocular Visual Odometry for On-Road Vehicles with 1-Point RANSAC. In Dynamic Maps. Dagstuhl Seminar Proceedings, Volume 10371, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{scaramuzza_et_al:DagSemProc.10371.3,
  author =	{Scaramuzza, Davide and Fraundorfer, Friedrich and Siegwart, Roland},
  title =	{{Real-Time Monocular Visual Odometry for On-Road Vehicles with 1-Point RANSAC}},
  booktitle =	{Dynamic Maps},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10371},
  editor =	{Claus Brenner and Wolfram Burgard and Marc Pollefeys and Christoph Stiller},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10371.3},
  URN =		{urn:nbn:de:0030-drops-29500},
  doi =		{10.4230/DagSemProc.10371.3},
  annote =	{Keywords: Structure from motion, visual odometry, SLAM, RANSAC, motion constraints}
}
  • Refine by Author
  • 2 Brenner, Claus
  • 2 Burgard, Wolfram
  • 2 Pollefeys, Marc
  • 2 Stiller, Christoph
  • 1 Fraundorfer, Friedrich
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms

  • Refine by Keyword
  • 2 Dynamic maps
  • 2 SLAM
  • 1 3D reconstruction
  • 1 3D scene perception
  • 1 Graph Algorithms
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 3 2011
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail