UNI Logo Bilder Heinz Nixdorf Institut
Algorithms and Complexity
Prof. Dr. math. Friedhelm Meyer auf der Heide
HNI Logo
Home > Research Groups > Prof. Dr. math. Friedhelm Meyer auf der Heide  > Projects
Smart Teams

Summary

In this project we aim at laying the algorithmic foundations for a scenario where an exploration team of robots we call it a smart team has to self-organize itself in order to fulfill tasks like exploring an unknown terrain and executing work in this terrain. Examples for such a task are rescue expeditions in dangerous areas or expeditions in the oceans or on planets. The work of such a smart team has to be guided by strategies for exploration, for finding important objects, and for assigning to such an object a subgroup of robots that jointly have the capabilities necessary to process the object. The challenge is that all these tasks have to be executed by local, distributed strategies that act on the mobile network of the moving robots, and have to result in a robust, effective selforganization of the team. None of these robots ever will have more than very restricted, local knowledge about the global state of the system. Their decisions are solely based on their own observations and findings, from which a globally good behavior of the whole team has to emerge. We will analyse the quality of our strategies both theoretically, e.g. by means of competitive analysis, and experimentally by extending  SAHNE, our simulation platform for communication in mobile ad hoc networks.

Background

The project was proposed in 2005 by Prof. Dr. Friedhelm Meyer auf der Heide and Prof. Dr. Christian Schindelhauer as a subproject of DFG SPP 1183: Organic Computing.
The full name of this project: "Smart Teams: Local Distributed Strategies for Self-Organizing Robotic Exploration Teams".

People

Smart Team Simulator

The Smart Team Simulator, developed in Java, cannot only simulate large swarms of robots on huge terrains, but can also present it in an impressive way. The RMI-enabled visualization covers both a 2d-view with helpful informations and a realistic 3d-view. Furthermore a customizable module for the representation of various statistic measured variables (e.g. as pie charts oder bar charts) is integrated. For developers a highly developed and easily understandable interface exists, allowing the efficient development of strategies for individual robots. A framework is available, which offers a library of frequently used robot actions (e.g. energy management or automatic orbiting of obstacles) and an easy to use interface to these. The simulator can be configured either comfortably using a GUI or using XML files.

The Smart Team simulator was developed by the project group  SmartTeams: Alexander Buss, Helena Deck, Miroslaw Dynia, Matthias Fischer, Holger Hagedorn, Peter Isaak, Alexander Krieger, Jaroslaw Kutylowski, Friedhelm Meyer auf der Heide, Viktor Nesterow, Adrian Ogierman, Jonas Schrieb, Boris Stobbe, Thomas Storm und Henning Wachsmuth.
For results refer to  Publication AMiRE 2007.

Simulator and Documentation

SmartS simulator

The SmartS simulator is part of the Smart Teams project. It is intended to simulate the Smart Teams scenario, with multiple robots working in some terrain. In SmartS, you can plug your strategies for robots into the general framework easily. This allows for quick development of new strategies. SmartS has been created by:

Publications of this Project


2011
Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; Warner, Daniel; Weddemann, Christoph; Wonisch, Daniel: A new Approach for Analyzing Convergence Algorithms for Mobile Robots. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Lecture Notes in Computer Science, volume 6756, pp. 650--661, July 2011, Springer-Verlag, Heidelberg, Germany (more)

Kling, Peter; Meyer auf der Heide, Friedhelm: Convergence of Local Communication Chain Strategies via Linear Transformations. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 159--166, 4 - 6 June 2011, ACM (more)

Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; Warner, Daniel; Weddemann, Christoph; Wonisch, Daniel: Collisionless Gathering of Robots with an Extent. In: 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), Lecture Notes in Computer Science, number 6543, pp. 178-189, 22 - 28 Jan 2011, Springer (more)

Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: Organic Computing — A Paradigm Shift for Complex Systems. , Autonomic Systems, volume 1, chapter Energy-Awareness in Self-organising Robotic Exploration Teams , pp. 531-543, Springer Verlag, 2011. Auflage, 2011 (more)

Degener, Bastian; Kempkes, Barbara; Langner, Tobias; Meyer auf der Heide, Friedhelm; Wattenhofer, Roger: A tight runtime bound for synchronous gathering of autonomous robots with limited visibility. In: SPAA '11: Proc. of the 23rd annual ACM symposium on parallel algorithms and architectures, pp. 139-147, 2011, ACM (more)

Brandes, Philipp; Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: Energy-efficient strategies for building short chains of mobile robots locally. In: SIROCCO '11: Proc. of the 18th International Colloquium on Structural Information and Communication Complexity, pp. 138-149, 2011 (more)


2010
Degener, Bastian; Gehweiler, Joachim; Lammersen, Christiane: Kinetic Facility Location. Algorithmica, 57(3): pp. 562-584, July 2010 (more)

Degener, Bastian; Kempkes, Barbara; Kling, Peter; Meyer auf der Heide, Friedhelm: A continuous, local strategy for constructing a short chain of mobile robots. In: SIROCCO '10: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, LNCS, volume 6058, pp. 168-182, 7 - 11 June 2010, Springer (more)

Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: A local O(n^2) gathering algorithm. In: SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 217-223, June 2010, ACM (more)

Miao, Huawei; Ooi, Chia Ching; Wu, Xiaowen; Schindelhauer, Christian: Coverage-hole Trap Model in Target Tracking using Distributed Relay-robot Network. In: Proc. of the 25th ACM Symposium on Applied Computing (SAC), pp. 1299-1304, Mar 2010 (more)

Brandes, Philipp; Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: Building short chains of mobile robots locally with a bounded stepwidth. 2010 (more)

Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter: A local, distributed constant-factor approximation algorithm for the dynamic facility location problem . In: International Parallel & Distributed Processing Symposium (IPDPS), 2010 (more)

Degener, Bastian: Local, distributed approximation algorithms for geometric assignment problems. International Graduate School of Dynamic Intelligent Systems, 2010 (more)


2009
Klaas, Alexander; Cord-Landwehr, Andreas; Raupach, Christoph; Weddemann, Christoph; Warner, Daniel; Wonisch, Daniel; Swierkot, Kamil; Märtens, Marcus; Hüllmann, Martina; Kling, Peter; Kurras, Sven: About Swarms. FRONTS-TR200955, Sep 2009 (more)

Brandes, Philipp: Theoretische und experimentelle Analyse einer lokalen Strategie für Roboter mit begrenzter Schrittweite zur Erzeugung einer optimalen Kommunikationskette. (more)

Bujna, Kathrin: Theoretische und experimentelle Analyse der Laufdistanz von Robotern bei der Bildung einer optimalen Kommunikationskette. (more)

Wistuba, Martin: Kontinuierliche lokale Strategien zur Minimierung vorhandener Kommunikationsnetzwerke zwischen mobilen Robotern. (more)

Mehler, Jan; Meyer auf der Heide, Friedhelm: Power-Aware Online File Allocation in Mobile Ad Hoc Networks. In: Proceedings of the 21st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'09), pp. 347-356, 11 - 13 Aug 2009 ACM SIGACT, ACM SIGARCH, ACM Press (more)

Bonorden, Olaf; Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter: Complexity and approximation of a geometric local robot assignment problem . In: Algorithmic Aspects of Wireless Sensor Networks, pp. 252 - 262, July 2009, Springer Verlag (more)

Ooi, Chia Ching; Schindelhauer, Christian: Minimal energy path planning for wireless robots. ACM/Springer Journal of Mobile Networks and Applications (MONET), May 2009 (more)

Kutylowski, Jaroslaw; Meyer auf der Heide, Friedhelm: Optimal strategies for maintaining a chain of relays between an explorer and a base camp . Theoretical Computer Science, 410(36): pp. 3391-3405 2009 (more)

Ooi, Chia Ching; Schindelhauer, Christian: Utilizing Detours for Energy Conservation in Mobile Wireless Networks. Springer Telecommunication Systems Journal, 43: pp. 25-37 2009 (more)

Bonorden, Olaf; Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter: Complexity and approximation of a geometric local robot assignment problem. tr-ri-09-299, 2009 (more)

Bienkowski, Marcin; Byrka, Jaroslaw ; Korzeniowski, Miroslaw; Meyer auf der Heide, Friedhelm: Optimal Algorithms for Page Migration in Dynamic Networks. Journal of Discrete Algorithms, 7(4): pp. 545-569 2009 (more)


2008
Ooi, Chia Ching; Schindelhauer, Christian: Energy-Efficient Distributed Target Tracking using Wireless Relay Robots. In: ARS'08: Proc. of the 9th International Symposium on Distributed Autonomous Robotic Systems (DARS 2008), Nov 2008, Springer (more)

Agne, Swetlana: Verteilte Graph Exploration unter unvollständiger Information. (more)

Pietrzyk, Peter: Lokale Strategien zur Optimierung von Kommunikationsketten. (more)

Meyer auf der Heide, Friedhelm; Schneider, Barbara: Local Strategies for connecting stations by small robotic networks. In: IFIP International Federation for Information Processing, Volume 268; Biologically- Inspired Collaborative Computing, pp. 95–104, Sep 2008, Springer Boston (more)

Schneider, Barbara: Lokale Strategien zur Aufrechterhaltung von Kommunikation zwischen mobilen Robotern. (more)

Ooi, Chia Ching; Schindelhauer, Christian: Detours Save Energy in Mobile Wireless Networks. In: MWCN'08: Proc. of IFIP Joint Conference on Mobile Wireless Communications Networks (MWCN 2008) and Personal Wireless Communications (PWC 2008), Jan 2008, Springer (more)

Degener, Bastian; Gehweiler, Joachim; Lammersen, Christiane: The Kinetic Facility Location Problem. In: Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT), pp. 378-389, 2008 (more)

Degener, Bastian; Gehweiler, Joachim; Lammersen, Christiane: The Kinetic Facility Location Problem. In: Proceedings of the 24th European Workshop on Computational Geometry, pp. 251-254, 2008 (more)

Degener, Bastian; Gehweiler, Joachim; Lammersen, Christiane: The Kinetic Facility Location Problem. tr-ri-08-288, Technical Report, 2008 (more)


2007
Dynia, Miroslaw: Collective Graph Exploration. Dissertation, Graduate School "Automatic Configuration in open systems", Dec 2007 (more)

Kutylowski, Jaroslaw: Using Mobile Relays for Ensuring Connectivity in Sparse Networks. Dissertation, International Graduate School of Dynamic Intelligent Systems, Dec 2007 (more)

Ooi, Chia Ching; Schindelhauer, Christian: Minimal energy path planning for wireless robots. In: ROBOCOMM'07: Proc. of the 1st International Conference on Robot Communication and Coordination, ACM International Conference Proceeding Series, Oct 2007, IEEE (more)

Baumann, Michael: Experimentelle Analyse der Chase-Explorer Strategie. (more)

Dynia, Miroslaw; Lopuszanski, Jakub; Schindelhauer, Christian: Why Robots Need Maps. In: Proc. of the 14th Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, pp. 37-- 46, 1 May 2007, Springer-Verlag Berlin (more)

Dynia, Miroslaw; Kutylowski, Jaroslaw; Meyer auf der Heide, Friedhelm; Schrieb, Jonas: Local strategies for maintaining a chain of relay stations between an explorer and a base station. In: SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, pp. 260-269, New York, NY, USA, 1 Jan 2007, ACM Press, New York, NY, USA (more)

Kutylowski, Jaroslaw: Competitive Maintenance of Minimum Spanning Trees under Stochastic Adversaries. , Jan 2007 (more)

Dynia, Miroslaw; Korzeniowski, Miroslaw; Kutylowski, Jaroslaw: Competitive Maintenance of Minimum Spanning Tree in Dynamic Graphs. In: Proc. of the 33rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'07), Lecture Notes in Computer Science, volume 4362, pp. 260--271, 1 Jan 2007, Springer-Verlag Berlin (more)

Schröder, Michael: Implementation of Radio Communication and Multi-hop Data Forwarding in PlayerStage Robot Simulator. (more)

Arens, Stephan; Buss, Alexander; Deck, Helena; Dynia, Miroslaw; Fischer, Matthias; Hagedorn, Holger; Isaak, Peter; Krieger, Alexander; Kutylowski, Jaroslaw; Meyer auf der Heide, Friedhelm; Nesterow, Viktor; Ogierman, Adrian; Schrieb, Jonas; Stobbe, Boris; Storm, Thomas; Wachsmuth, Henning: Smart Teams: Simulating Large Robotic Swarms in Vast Environments. In: 4th International Symposium on Autonomous Minirobots for Research and Edutainment (AMiRE 2007), pp. 215-222, 2007 (more)

Bienkowski, Marcin; Kutylowski, Jaroslaw: The k-Resource Problem on Uniform and on Uniformly Decomposable Metric Spaces. In: Proc. of the 10th International Workshop on Algorithms and Data Structures (WADS), LNCS, pp. 337-348, 1 Jan 2007, Springer-Verlag Berlin (more)


2006
Dynia, Miroslaw; Kutylowski, Jaroslaw; Lorek, Pawel; Meyer auf der Heide, Friedhelm: Maintaining Communication Between an Explorer and a Base Station. In: IFIP 19th World Computer Congress, TC10: 1st IFIP International Conference on Biologically Inspired Computing, pp. 137--146, 1 Jan 2006 (more)

Dynia, Miroslaw; Kumlehn, Andreas; Kutylowski, Jaroslaw; Meyer auf der Heide, Friedhelm; Schindelhauer, Christian: SmartS Simulator Design. , Jan 2006 (more)

Dynia, Miroslaw; Kutylowski, Jaroslaw; Schindelhauer, Christian; Meyer auf der Heide, Friedhelm: Smart Robot Teams Exploring Sparse Trees. In: Proc. of the 31st International Symposium of Mathematical Foundations of Computer Science, Springer Lecture Notes in Computer Science LNCS, pp. 327-338, Jan 2006, Springer Verlag (more)

Dynia, Miroslaw; Korzeniowski, Miroslaw; Schindelhauer, Christian: Power-Aware Collective Tree Exploration. In: Proc. of the Architecture of Computing Systems, LNCS, number 3894, pp. 341--351, Jan 2006, Springer Verlag (more)



to top