2 Search Results for "Werner, Nils"

Document
DOI: 10.4230/LIPIcs.ESA.2022.89
Combining Predicted and Live Traffic with Time-Dependent A* Potentials

Authors: Nils Werner and Tim Zeitz

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We study efficient and exact shortest path algorithms for routing on road networks with realistic traffic data. For navigation applications, both current (i.e., live) traffic events and predictions of future traffic flows play an important role in routing. While preprocessing-based speedup techniques have been employed successfully to both settings individually, a combined model poses significant challenges. Supporting predicted traffic typically requires expensive preprocessing while live traffic requires fast updates for regular adjustments. We propose an A*-based solution to this problem. By generalizing A* potentials to time dependency, i.e. the estimate of the distance from a vertex to the target also depends on the time of day when the vertex is visited, we achieve significantly faster query times than previously possible. Our evaluation shows that our approach enables interactive query times on continental-sized road networks while allowing live traffic updates within a fraction of a minute. We achieve a speedup of at least two orders of magnitude over Dijkstra’s algorithm and up to one order of magnitude over state-of-the-art time-independent A* potentials.
Cite as

Nils Werner and Tim Zeitz. Combining Predicted and Live Traffic with Time-Dependent A* Potentials. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 89:1-89:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{werner_et_al:LIPIcs.ESA.2022.89,
  author =	{Werner, Nils and Zeitz, Tim},
  title =	{{Combining Predicted and Live Traffic with Time-Dependent A* Potentials}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{89:1--89:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.89},
  URN =		{urn:nbn:de:0030-drops-170271},
  doi =		{10.4230/LIPIcs.ESA.2022.89},
  annote =	{Keywords: realistic road networks, shortest paths, live traffic, time-dependent routing}
}
Document
DOI: 10.4230/OASIcs.KiVS.2011.26
A Service-Oriented Operating System and an Application Development Infrastructure for Distributed Embedded Systems

Authors: Martin Lipphardt, Nils Glombitza, Jana Neumann, Christian Werner, and Stefan Fischer

Published in: OASIcs, Volume 17, 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)

Abstract
The paradigm of service-orientation promises a significant ease of use in creating and managing distributed software systems. A very important aspect here is that also application domain experts and stakeholders, who are not necessarily skilled in computer programming, get a chance to create, analyze, and adapt distributed applications. However, up to now, service-oriented architectures have been mainly discussed in the context of complex business applications. In this paper we will investigate how to transfer the benefits of a service-oriented architecture into the field of embedded systems, so that this technology gets accessible to a much wider range of users. As an example, we will demonstrate this scheme for sensor network applications. In order to address the problem of limited device resources we will introduce a minimal operating system for such devices. It organizes all pieces of code running on a sensor node in a service-oriented fashion and also features the relocation of code to a different node at runtime. We will demonstrate that it is possible to design a sensor network application from a set of already existing services in a highly modular way by employing already existing technologies and standards.
Cite as

Martin Lipphardt, Nils Glombitza, Jana Neumann, Christian Werner, and Stefan Fischer. A Service-Oriented Operating System and an Application Development Infrastructure for Distributed Embedded Systems. In 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011). Open Access Series in Informatics (OASIcs), Volume 17, pp. 26-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{lipphardt_et_al:OASIcs.KiVS.2011.26,
  author =	{Lipphardt, Martin and Glombitza, Nils and Neumann, Jana and Werner, Christian and Fischer, Stefan},
  title =	{{A Service-Oriented Operating System and an Application Development Infrastructure for Distributed Embedded Systems}},
  booktitle =	{17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)},
  pages =	{26--37},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-27-9},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{17},
  editor =	{Luttenberger, Norbert and Peters, Hagen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.KiVS.2011.26},
  URN =		{urn:nbn:de:0030-drops-29550},
  doi =		{10.4230/OASIcs.KiVS.2011.26},
  annote =	{Keywords: service-oriented OS, sensor network, distributed embedded systems}
}
  • Refine by Author
  • 1 Fischer, Stefan
  • 1 Glombitza, Nils
  • 1 Lipphardt, Martin
  • 1 Neumann, Jana
  • 1 Werner, Christian
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 1 distributed embedded systems
  • 1 live traffic
  • 1 realistic road networks
  • 1 sensor network
  • 1 service-oriented OS
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2011
  • 1 2022

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact