CMPT882 Distributed Robot Systems

Graduate seminar class on distributed autonomous systems

Ideas for class projects

Stage at GitHub
Stage docs

View the Project on GitHub rtv/822

Objectives

Students will understand:
  1. the applications and challenges of building systems of multiple robots and/or sensors;
  2. the major approaches from the literature;
  3. motivating examples from nature.

Students will implement their own multi-robot system in a research-paper-style project.

Topics

Outline

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.

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

  1. Craig Reynolds, Flocks, Herds, and Schools: A Distributed Behavioral Model, Computer Graphics, 21(4) 1987 (SIGGRAPH '87 Conference Proceedings) pages 25-34. Homepage
  2. Leslie Lamport, Time, clocks and the ordering of events in a distributed system, Communications of the ACM 21, 7 (July 1978), 558-565. PDF
  3. 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
  4. Richard Vaughan, Massively Multi-Robot Simulations in Stage,Swarm Intelligence 2 (2-4) :189-208 December 2008 PDF

Week 2: Ant algorithms and relatives

  1. 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.
  2. 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
  3. J. Svennebring and S. Koenig. Building terrain-covering ant robots. Autonomous Robots, 16, (3), 313-332, 2004. PDF (alternative shorter ICRA paper: PDF)
  4. 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:

  1. 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
  2. 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
  3. 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
  4. 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

  1. 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

  1. 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.
  2. 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.
  3. David Payton , Regina Estkowski , Mike Howard Compound Behaviors in Pheromone Robotics Robotics and Autonomous Systems, 2001, 44, pp.229--240. PDF
  4. 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.
  5. 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
  6. 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).
  7. Tucker Balch, Ronald Arkin Behaviour-based Formation Control for Multi-Robot Teams, IEEE Transactions on Robotics and Automation, 14:6 pp926-939, 1998. PDF
  8. 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
  9. 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
  10. 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
  11. 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

Week 9: Human-multi-robot interaction

Other resources