multi-agent robotic systems in logistics · MIN-Fakultät FachbereichInformatik multi-agent robotic...

MIN-FakultätFachbereich Informatik

multi-agent robotic systems in logisticsa look at kiva systems and amazon robotics

robert a. brown

Universität HamburgFakultät für Mathematik, Informatik und NaturwissenschaftenFachbereich InformatikTechnische Aspekte Multimodaler Systeme

28. november 2016

r. brown – intelligent robotics 1 / 20

What are Multi-Robotic Systems?What are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

exactly what they sound like!I coordination between large groups of relatively simple robots

I working together towards common goalI not necessarily cooperative or communicativeI local strategies

I draws inspiration from swarms found in natureI fish, birds, ants

I cooperative systemsI communicate goals

I self-interested systemsI compete for resources in

market-based environment

[Loo15]

r. brown – intelligent robotics 2 / 20

Can a thousand tiny swarming robots outsmart nature?What are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

https://www.youtube.com/watch?v=dDsmbwOrHJs

r. brown – intelligent robotics 3 / 20

Modeling SwarmsWhat are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

Brownian Motion as a PDE∂p∂t = D∆p

∂p∂t =

v2µ

(∂2p∂x2 +

∂2p∂t2 )

...with a Poison Processµ

2 ptt + ptt =v2µpxx

These types of complex systemscomposed of simple actors canbe mmodeled as dynamicsystems, and studying theirinteraction is a field unto itself...

Dynamic System Representing a Swarm of Locusts [Ek01]

r. brown – intelligent robotics 4 / 20

What are Multi-Robotic Systems?What are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

The group of robots is notjust a group. It has somespecial characteristics,which are found in swarmsof insects, that is,decentralised control,lack of synchronisation,simple and IdenticalMembers [Ben05]

Taxonomies of Swarm Robotics [BFBD13]

r. brown – intelligent robotics 5 / 20

Chaotic StorageWhat are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

[Urd12]r. brown – intelligent robotics 6 / 20

Chaotic StorageWhat are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

https://www.youtube.com/watch?v=ZxrzIXkPycs

r. brown – intelligent robotics 7 / 20

The Kiva WarehouseWhat are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

I RackI organized using chaotic

storageI storage unit

I Robotic Agent (“Driver”)I brings Racks to the PickerI returns rack to floor

I PickerI No longer fetches products

Example of a Kiva Systems Rack, Driver, and Picker

[WDM07]

r. brown – intelligent robotics 8 / 20

The Kiva WarehouseWhat are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

Example of a Kiva Warehouse Floor Plan [WDM07]

r. brown – intelligent robotics 9 / 20

The Kiva WarehouseWhat are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

https://www.youtube.com/watch?v=z_R8feyCu-M

r. brown – intelligent robotics 10 / 20

Kiva Systems Softwarewhat does the system need to do?What are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

I actors must handle their ownlocal tasks

I manage resourcesI space on racksI space on the floorI robot units

I manage task assignments

Interaction between layers of Kiva Warehouse [WDM07]

r. brown – intelligent robotics 11 / 20

Kiva Systems Softwarewhat do the actors need to do?What are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

I find a path to the desiredproductsI uses A* algorithm (simple,

greedy, heuristic based “AI”)I navigate their environment

I follows stickers on the floorI localization not neededI already knows map

I not hit each other[Urb]

r. brown – intelligent robotics 12 / 20

Kiva Systems SoftwareWhat are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

The Kiva Warehouse “Driver” [Gui08]

r. brown – intelligent robotics 13 / 20

The Kiva WarehouseWhat are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

ProsI Greater accountabilityI No single point of failureI Optimization based on

PopularityI Rapid deploymentI Spatial flexibilityI Expandability

ConsI Can’t pick things up

r. brown – intelligent robotics 14 / 20

Kiva Systems SoftwareWhat are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

https://www.youtube.com/watch?v=fwghi0jpKkYq

r. brown – intelligent robotics 15 / 20

ConclusionWhat are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

I Multi Agent Systems work independently to complete commongoalI may or may not communicateI share resources

I Kiva systems uses MAS and surprisingly simple/primitive/oldalgorithmsI real breakthrough was the idea (and cheaper robots)

I Kiva Warehouses store up to 200% storage capacity andproductivity, as well as accountability [Gui08]

r. brown – intelligent robotics 16 / 20

BibliographyWhat are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

[Ben05] Gerardo Beni.From swarm intelligence to swarm robotics.In Proceedings of the 2004 International Conference onSwarm Robotics, SAB’04, pages 1–9, Berlin,Heidelberg, 2005. Springer-Verlag.

[BFBD13] Manuele Brambilla, Eliseo Ferrante, Mauro Birattari,and Marco Dorigo.Swarm robotics: a review from the swarm engineeringperspective.Swarm Intelligence, 7(1):1–41, 2013.

r. brown – intelligent robotics 17 / 20

Bibliography (cont.)What are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

[Ek01] Leah Edelstein-keshet.Mathematical models of swarming and socialaggregation, invited lecture.In The 2001 International Symposium on NonlinearTheory and its Applications, 2001.

[Gui08] Eric Guizzo.Three engineers, hundreds of robots, one warehouse.IEEE Spectrum, 45(7):26 – 34, 2008.

[Loo15] Deep Look.Can a thousand tiny swarming robots outsmart nature?| deep look.https://www.youtube.com/watch?v=dDsmbwOrHJs,2015.

r. brown – intelligent robotics 18 / 20

Bibliography (cont.)What are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

[Urb] UrbanExile.Butter robot from ”something ricked this way comes”.https://www.reddit.com/r/rickandmorty/comments/33incc/butter_robot_from_something_ricked_this_way_comes.Accessed: 2016-12-01.

[Urd12] Yes Urdu.Inside amazon’s warehouse.http://en.yesurdu.com/buzz/misc-fun/inside-amazons-warehouse/, 2012.

r. brown – intelligent robotics 19 / 20

Bibliography (cont.)What are Multi-Robotic Systems? The Warehouse Problem The Kiva Warehouse Conclusion Bibliography

[WDM07] Peter R. Wurman, Raffaello D’Andrea, and MickMountz.Coordinating hundreds of cooperative, autonomousvehicles in warehouses.In Proceedings of the 19th National Conference onInnovative Applications of Artificial Intelligence -Volume 2, IAAI’07, pages 1752–1759. AAAI Press,2007.

r. brown – intelligent robotics 20 / 20