Objectives
Students will understand:
- the applications and challenges of building systems of multiple robots and/or sensors;
- the major approaches from the literature;
- motivating examples from nature.
Students will implement their own multi-robot system in a research-paper-style project.
Topics
- multi-robot systems
- sensor networks
- software engineering for distributed systems
- control and coordination models for multi-agent systems, including
- explicit consensus models
- swarm approaches
- applications & challenges
Outline
- seminar class based on research papers
- students present and critique papers
- one short programming homework to learn Stage
- project: implement and experiment with a multi-robot system or sensor network in simulation (or on real hardware if available)
Programming homework - Demo on Wed 24 Jan
Project: multi-robot system in simulation.
Implement an existing idea or - better - an extension of prior work or a novel idea, in simulation, and perform experiments to evaluate it.
- Describe project proposal to class 21 February (after reading break)
- Demo to class in last week of class
- Write a 6 page conference-style paper, due 13 April.
Presention schedule
Every student will present one paper from the reading list to the class, and lead a discussion about it. The schedule will appear here, following discussion in class on 24 Jan.
Reading List
Week 1: embodied distributed concensus with robots greatest hits
- Craig Reynolds, Flocks, Herds, and Schools: A Distributed Behavioral Model, Computer Graphics, 21(4) 1987 (SIGGRAPH '87 Conference Proceedings) pages 25-34. Homepage
-
Leslie Lamport, Time, clocks and the ordering of events in a distributed system, Communications of the ACM 21, 7 (July 1978), 558-565.
PDF
- Andrew Howard, Maja J. Matarić and Gaurav S. Sukhatme. "An Incremental Self-Deployment Algorithm for Mobile Sensor Networks". In Autonomous Robots Special Issue on Intelligent Embedded Systems, 13(2):113-126, 2002.
PDF
- Richard Vaughan,
Massively Multi-Robot Simulations in Stage,Swarm Intelligence 2 (2-4) :189-208 December 2008 PDF
Week 2: Ant algorithms and relatives
-
M. Dorigo ; V. Maniezzo ; A. Colorni, Ant system: optimization by a
colony of cooperating agents. IEEE Transactions on Systems, Man, and
Cybernetics, Part B (Cybernetics) ( Volume: 26, Issue: 1, Feb 1996 )
PDF Marco Dorigo's web site.
- Mayet, Ralf, et al. "Antbots: A feasible visual emulation of pheromone trails for swarm robots." International Conference on Swarm Intelligence. Springer Berlin Heidelberg, 2010. PDF
- J. Svennebring and S. Koenig. Building terrain-covering ant robots. Autonomous Robots, 16, (3), 313-332, 2004.
PDF
(alternative shorter ICRA paper: PDF)
- Vaughan, K. Stoy, G. Sukhatme, and M. Mataric. LOST: Localization-space trails for robot teams. IEEE Transactions on Robotics and Automation, 18(5):796-812, 2002. PDF
Extensions and published former class projects:
-
Abbas Sadat, Richard Vaughan. SO-LOST: An ant-trail algorithm for multi-robot navigation with active interference reduction
Proc. Twelfth Int. Conf. on Artificial Life (ALife XII), August 2010 PDF
- Zhao Song, Seyed Abbas Sadat, Richard Vaughan. MO-LOST: Adaptive ant trail untangling in multi-objective multi-colony robot foraging
Proc. Eleventh Int. Conf. on Autonomous Agents and Multiagent systems, Valencia, Spain June 2012 PDF
-
Alaa Eldin Abdelaal, Maram Sakr, Richard Vaughan. LOST Highway: a Multiple-Lane Ant-Trail Algorithm to Reduce Congestion in Large-Population Multi-Robot Systems
Conference on Computer and Robot Vision, (CRV'17), Edmonton, AB, Canada , May 2017
PDF
- Geoff Nagy, Richard Vaughan. Self-Organization of a Robot Swarm into Concentric Shapes
Conference on Computer and Robot Vision, (CRV'17), Edmonton, AB, Canada , May 2017
PDF
Week 3: Energy management
- Yaroslav Litus, Richard Vaughan, Pawel Zebrowski.
The Frugal Feeding Problem: Energy-efficient, multi-robot, multi-place rendezvous
Proc. IEEE Int. Conf. on Robotics and Automation, April 2007 PDF
PDF
Week 4: Collective manipulation
Week 5: Formation control & task allocation
- Michael Rubenstein, Alejandro Cornejo, Radhika Nagpal,
Programmable Self-Assembly in a Thousand-Robot Swarm
Science, Vol 345, no 6198, 15 Aug 2014 Link to fetch "Open" copy.
- Edwin Olson, Johannes Strom, Ryan Morton, Andrew Richardson, Pradeep Ranganathan, Robert Goeddel, Mihai Bulic, Jacob Crossman and Bob Marinier, Progress towards multi-robot reconnaissance and the MAGIC 2010 Competition Journal of Field Robotics, 29:5, pp.762--792, September 2012,
PDF.
- David Payton , Regina Estkowski , Mike Howard
Compound Behaviors in Pheromone Robotics
Robotics and Autonomous Systems, 2001, 44, pp.229--240. PDF
- All time classic
Craig W. Reynolds
Flocks, Herds, and Schools: A Distributed Behavioral Model
Computer Graphics, 21(4), pp25-34, July 1987,
HTML version
Original video Craig's long-maintained Boids page is a treasure trove.
- Excellent recent paper Hyongju Park, Seth Hutchinson
A Distributed Robust Convergence Algorithm for Multi-Robot Systems in the Presence of Faulty Robots 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2015 2980-2985.
IEEE Xplore (works inside SFU
- Martin Saska, Vojtech Vonasek, Jan Chudoba, Justin Thomas, Giuseppe Loianno, Vijay Kumar
Swarm Distribution and Deployment for Cooperative
Surveillance by Micro-Aerial Vehicles
Journal of Intelligent Robot Systems, doi:10.1007/s10846-016-0338-z, 2016.
PDF (Kumar also has Ted talks and other popular talks on YouTube going over a large body of work).
- Tucker Balch, Ronald Arkin
Behaviour-based Formation Control for Multi-Robot Teams, IEEE Transactions on Robotics and Automation, 14:6 pp926-939, 1998. PDF
- Brian Gerkey, Maja Mataric
A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems, International Journal of Robotics Research, 23:9 pp939-954, 2004. PDF
- Jacob Fredslund, Maja Mataric
A General Algorithm for Robot Formations Using
Local Sensing and Minimal Communication
IEEE Transactions on Robotics and Automation, 18:5, October 2002.
IEEE Xplore (works inside SFU
-
Richard Vaughan, Neil Sumpter, Jane V. Henderson, Andy Frost, Stephen Cameron.
Experiments in Automatic Flock Control
Robotics and Autonomous Systems 31 :109-117 2000 PDF VIDEO
- Former class project
Pawel Zebrowski, Yaroslav Litus, Richard Vaughan.
Energy Efficient Robot Rendezvous,
Proc. Fourth Canadian Conference on Computer and Robot Vision, May 2007 PDF
Week 6: Multi-robot coordination for high-level tasks
Week 7: Modular robots
Week 8: Controlling external distributed systems