Vortrag von Christian Bettstetter beim Austrian Computer Science Day am 20.06.2017 in Wien

Spätestens seit der Ankündigung von Amazon Prime Air im Jahr 2013 ist die automatisierte Lieferung von Gütern mithilfe kleiner, autonomer Drohnen in aller Munde. Besonders interessant sind drohnenbasierte Lieferdienste für die Zustellung wichtiger, dringend benötigter Güter im ländlichen Raum mit schlechter Verkehrsinfrastruktur und in staugeplagten Großstädten. So werden beispielsweise Krankenhäuser in Ruanda vom Silicon-Valley-Startup Zipline auf diese Weise mit Medikamenten beliefert. Und das 2011 gegründete Unternehmen Matternet entwickelt zusammen mit Mercedes-Benz einen kostengünstigen, vollautomatisierten Drohnentransport für die “letzte Meile” zum Kunden.

Im Rahmen unserer multidisziplinären Aktivitäten zu Multidrohnensystemen im Forschungsschwerpunkt “Vernetzte und Autonome Systeme” der Universität Klagenfurt und der Lakeside Labs GmbH beschäftigen wir uns neben anderen Themen mit solchen Lieferdiensten. Unser spezielles Augenmerk gilt der automatisierten Aufgabenverteilung in einem Netzwerk von Drohnen. Dieses Thema möchte ich in diesem zwanzigminütigen Vortrag kurz vorstellen.

Abstrakt betrachtet analysieren wir ein System mit Gütern, Kunden, Transportmitteln und Depots. Die Kunden fordern Güter an, die in Depots gelagert sind. Diese Anfragen (Jobs) treten zeitlich und räumlich zufällig auf. Die Transportmittel arbeiten diese Anfragen ab und liefern das gewünschte Gut an den Kunden. Hierzu ist die Zuteilung eines Jobs an ein Transportmittel nötig, was wir Job Selection nennen.

Lassen Sie mich einige unserer Ergebnisse zusammenfassen: Wenn immer die älteste Anfrage als nächstes bedient wird (first job first), kann es passieren, dass das System schon beim Ausfall eines einzigen Transportmittels instabil wird. Bedient man hingegen immer die örtlich nächste Anfrage (nearest job first), tritt ein solcher Schwelleneffekt (tipping point behavior) nur in einigen Szenarien auf. Zudem kann ein nearest job first-Verfahren sehr gut in verteilter Weise implementiert werden, so dass jedes Transportmittel selbst entscheidet, welche Anfrage sie als nächstes abarbeitet, wodurch sich der Grad der Autonomie über das rein autonome Fliegen hinaus erhöht. Während der Zeitpunkt der Job Selection bei der Verwendung von first job first deutlichen Einfluss auf die Lieferzeit und die Systemstabilität hat, ist er bei nearest job first bedeutungslos.

Basierend auf diesen Ergebnissen stellen wir eine Methodik zur Dimensionierung eines dronenbasierten Lieferdiensts vor, wie sie zum Beispiel von einer Firma für die Planung des Systems verwendet werden kann. Dabei werden die monetären Kosten in Verhältnis zur erwarteten Lieferzeit gesetzt. Es werden drei Zeithorizonte berücksichtigt: die Anzahl der Depots (langfristiges Investment), die Anzahl der Transportmittel (mittelfristiges Investment) und die verwendete Job Selection (sehr kurzfristig änderbar).

Publikation

Pasquale Grippa, Doris A. Behrens, Christian Bettstetter, Friederike Wall:
Job Selection in a Network of Autonomous UAVs for Delivery of Goods.
Im Konferenzband Robotics: Science and Systems, MIT, Cambridge, MA, USA, Juli 2017.

Referent

Christian Bettstetter ist Professor an der Universität Klagenfurt und leitet dort das Institut für Vernetzte und Eingebettete Systeme an der Fakultät für Technische Wissenschaften. Er ist zudem wissenschaftlicher Leiter der Lakeside Labs GmbH. Mit seinem Team beschäftigt er sich mit der allgegenwärtigen Vernetzung von mobilen Geräten, Sensoren und autonomen Fluggeräten sowie mit interdisziplinären Fragestellungen für selbstorganisierende vernetzte Systeme. Er studierte Elektro- und Informationstechnik an der Technischen Universität München und promovierte dort am Lehrstuhl für Kommunikationsnetze mit dem Prädikat summa cum laude. Während dieser Zeit sammelte er USA-­Erfahrung bei Wacker Siltronic und der University of Notre Dame. Nach der Promotion arbeitete er am europäischen Forschungszentrum von NTT DOCOMO. Im Alter von 32 Jahren folgte er einem Ruf auf den neu zu gründenden Lehrstuhl für Mobile Systeme in Klagenfurt. Herr Bettstetter verfasste mehr als 130 Fachartikel und ist Mitautor eines bekannten Lehrbuchs zum Mobilfunksystem GSM. Mehrere Publikationen wurden mit Preisen ausgezeichnet; drei davon werden über 1.000 Mal zitiert. Der 44‑jährige gebürtige Bayer lebt zusammen mit seiner Partnerin und zwei Töchtern in Klagenfurt am Wörthersee.