Topics in MultiRobotics


(CS 236604, Advanced Topics #4 in CS)

URL:  http://www.cs.technion.ac.il/~wagner/pub/mrseminar.html
Spring  2005
Last update: June 13, 2005


Contents

  1. General
  2. Pre-Requisites
  3. Requirements
  4. Notes to students
  5. Schedule
  6. List of topics
  7. Resources


 

General


In this seminar/course we shall study the ideas, behavior and performance of robots and teams of robots. Starting with basic terms, we shall go over some abstract ideas of cooperation, and then study specific tasks, e.g. sorting, covering and pattern formation. For each task we shall consider both theoretical and experimental results, and a stress will be given, wherever possible,  to mathematical models of such teams.
For details and examples, see the list of topics.

Class: Taub 03, Tuesday 8:30-10:30

Coordinators:

  1. Dr. Israel Wagner
    email: wagner@cs.technion.ac.il
    Tel: 8296331
    Reception: Taub 720, Tuesday 11:00-12:00, by appointment (via phone or email)
     
  2. Prof. Freddy Bruckstein


PreRequisites

  1. graph algorithms
  2. calculus 2 ("CHEDVA 2")

Requirements

  1. attending classes
  2. presenting a paper to the class
  3. writing a summary of the presented paper
  4. doing a final homework

Notes to students

  1. There will be no meeting on the third week (22.3.2003)
  2. Background material list in CS library website
  3. An outline of your presentation (list of sub-topics, time for each) should be e-mailed to me, at least one week before presenting it in class.
  4. Instructions for preparing your duties for the MultiRobotics seminar
    Please read carefully.

In this course, in addition to attending the class,
you have to do three things:
 

    1. Presenting a topic, according to guidelines given in class
    2. Running a simulation excercise:
      You have to choose a problem from the topic you presented and run a simulation program to investigate the problem. The programming language is up to you, but you have to report it in a very clear way. Your report should include:
      1. problem definition and background: where does it come from, why is it of interest, why simulation is a good way to investigate this problem
      2. the structure of your simulation program
      3. the results and what can be learned from them
      4. discussion of further investigations that can be done of this problem
    3. submitting a final report, including:
      1. your presentation in class
      2. a detailed report of your simulation work
    4. Together with your simulation result, you should add the answers to the questionnaire

For any question, please email.


Schedule

date

week 

topic  

presentor(s)

 

8/3

1

no meeting

 

 

15/3

2

introduction and basics

 

israel

22/3

3

no meeting

 

 

29/3

4

ant robotics: cycles, robustness, and randomness

 

israel

 

5/4

5

random walk

israel

12/4

6

robotic firefighters

how to present a paper

yaniv

israel

19/4

7

terms and concepts

sorting

zlotnik

cohen, weiss

3/5

8

teamwork

motion planning and navigation

shelef, dayan

netzer

10/5

9

covering(a)

covering (b)

ochayon

weinberg, apfelbaum

17/5

10

multirobot trajectory planning

hunting

belous, koblenc

beder, pitalko

24/5

11

Yom ha-student  -  no meeting

 

31/5

12

positioning (a)

shape and order

avraham

regev

7/6

13

formation and dynamical systems

how to submit your simulation

zlochin

israel

14/6

14

graphbots

pursuit

fishman

nussbaum,  issan

21/6

15

Efficient task allocation for multirobot teams

models of control

yaniv

reznikov

 

 

 

 

 

 

 

 

 

Note: some presentations are accessible here


A list of topics

  1. Terms and Concepts
    1. G. Dudek et. al.: "A Taxonomy for Multi-Agent Robotics", Autonomous Robots 3, pp. 375-397 (1996)
    2. R. Brooks: "Fast, Cheap and Out of Control: A Robot Invasion of the Solar System"
      Journal of the British Interplanetary Society, Vol. 42, pp. 478-485, (1989).
  2. Shape and Order
    1. I. A. Wagner, A. M. Bruckstein: "Row Straightening via Local Interactions" Circuits, Systems, and Signal Processing, Vol. 16, No. 3, 1997.
    2. I. Suzuki and M. Yamashita: "Distributed Anonymous Mobile Robots: Formation of Geometric Patterns", SIAM Journal on Computing, Vol. 28 No.4, pp. 1347-1363 (1999)
    3. H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita: "Distributed Memoryless Point Convergence Algorithm for Mobile Robots with Limited Visibility", IEEE Transactions on  Robotics and Automation, Vol 15, No 5, October 1999, pp. 818-828.
    4. [A. M. Bruckstein, G. Sapiro, D. Shaked:"Evolution of Planar Polygons", Int. J. of Pattern Recognition and AI, Vol. 9 No. 6 (1995) pp. 991-1014. ]
  3. Sorting
    1. J.L. Deneubourg et. al.: "The Dynamics of Collective Sorting: Robot-Like Ants and Ant-Like Robots", First International Conference on Simulation of Adaptive Behaviors, pp. 356-363.
    2. O. Holland and C. Melhuish: "Stigmergy, self-organisation, and sorting in collective robotics", Artificial Life, 5(2):173 202, 1999.
  4. Models of Control
    1. V. Braitenberg: "Vehicles", MIT Press (1984)
    2. A. Casal, M. Yim: "Self reconfiguration planning for a class of modular robots", Proc. SPIE - Int. Soc. Opt. Eng. (USA) Vol. 3839 1999 P246-57.
    3. Yim, M.; Duff, D.G.; Roufas, K.D: "PolyBot: a modular reconfigurable robot", Robotics and Automation, 2000. Proceedings. ICRA '00, Page(s): 514 -520 vol.1.
  5. Covering and Exploration (a)
    1. I. A. Wagner, A. M. Bruckstein: "Cooperative Cleaners: A Case of Distributed Ant-Robotics" in "Communications, Computation, Control, and Signal Processing: A Tribute to Thomas Kailath," Kluwer Academic Publishers, The Netherlands, 1997, pp. 289-308.
    2. R. Baeza-Yates, R. Schott: "Parallel Searching in the Plane" Computational Geometry 5 (1995) pp. 143-154.
  6. Covering and Exploration (b)
    1. I. A. Wagner, M. Lindenbaum, A. M. Bruckstein: "Efficiently Searching a Graph by a Smell-Oriented Vertex Process", Annals of Mathematics and Artificial Intelligence 24 (1998) pp. 211-223
    2. I. A. Wagner, M. Lindenbaum, A. M. Bruckstein: "ANTS: Agents, Networks, Trees, and Subgraphs" Future Generation Computer Systems journal, Special issue on Ant Colony Optimization, North Holland, June 2000, Vol. 16 No. 8, pp. 915-926.
    3. I. A. Wagner, M. Lindenbaum, A. M. Bruckstein: "MAC vs. PC - Determinism and Randomness as Complementary Approaches to Robotic Exploration of Continuous Unknown Domains,"  ,  IJRR - International Journal of Robotics Research, Volume: 19, Number: 1, January 2000, pp. 12-31
  1. Motion Planning and Navigation
    1. Th. Fraichard, Y. Demazeau: "Motion Planning in a Multi-Agent World", in Decentralized AI, Y. Demazeau & J. P. Muller (Eds.), Elsevier 1990, pp. 137-153
    2. Y. Fujita et. al. : "Learning-Based Automatic Generation of Collision Avoidance Algorithms for Multiple Autonomous Mobile Robots", IROS'98 pp.1553-1558 October 1998.
  2. Teamwork
    1. Y. Shoham, M. Tenenholtz: "On Social Laws for Artificial Agent Societies: Off-Line Design" Artificial Intelligence, Vol. 73 (1995) pp. 231-252.
    2. T. Minami, I. Suzuki, M. Yamashita: "Fusion of Social Laws and Super Rules for Coordinating the Motion of Mobile Robots", IROS-96, pp. 1691-1698
    3. S. Marsella et. al. :"On Being a Teammate: Experiences Acquired in the Design of RoboCup Teams", Autonomous Agents-99, pp. 221-227.
  3. Routing in VLSI and Robotics
  4. Multirobot trajectory planning: path-velocity revisited
    1. Th. Fraichard, "Trajectory Planning in a Dynamic Workspace: a 'State-Time Space' Approach", Advanced Robotics,  13(1):75-94, 1999.
    2. Th. Fraichard, "Trajectory planning amidst moving obstacles: path-velocity decomposition revisited", Journal of the Brazilian Computer Science Society, special issue on Robotics, 4(3):5-13,  April 998.
  5. Pursuit
    1. A. M. Bruckstein: "Why Ant Trails Look So Straight and Nice", The Mathematical Intelligencer 15, No. 2, pp. 59-62 (1993)
    2. A. M. Bruckstein, C. L. Mallows, I. A. Wagner: "Probabilistic Pursuits on the Grid" American Mathematical Monthly 104, No. 4 , pp. 323-343 (1997)
  6. Hunting
    1. H. Yamaguchi: "Cooperative Hunting Behavior by Mobile-Robot Troops" IJRR 18(20), September 1999, pp. 931-940.
  7. Formation and dynamical systems
    S. Monteiro, E. Bicho: “A Dynamical Systems Approach to Behavior-Based Formation Control”, ICRA 2002,  pp. 2606-2611, and more details in chapter 4 of Estella Bicho's thesis
  8. Positioning (a)
    1. J. Borenstein, L. Feng: "Measurement and Correction of Systematic Odometry Errors in Mobile Robots." IEEE Journal of Robotics and Automation, Vol 12, No 6, December 1996, pp. 869-880. (and see http://www-personal.engin.umich.edu/~johannb/ )
  9. Positioning (b)
    1. R. Kurazume, S. Nagata: "Cooperative Positioning with Multiple Robots" ICRA 1994, pp. 1250-1257.
    2. T. Andou: "Andhill-98: A RoboCup Team which Reinforces Positioning with Observation" RoboCup-98, Springer Verlag
  10. Graphbots
    1. S. Khuller, E. Rivlin, A. Rosenfeld: "Graphbots: Cooperative Motion Planning in Discrete Spaces" IEEE T. on Systems. Man and Cybernetics-Part C, Vol. 28, No. 1, February 1998.
  11. Efficient task allocation for multirobot teams

1.      Brian P. Gerkey and Maja J. Mataric, "Sold!: Auction Methods for Multirobot Coordination", IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 18, NO. 5, OCTOBER 2002.

2.       Thomas Lemaire, Rachid Alami, Simon Lacroix, "A Distributed Tasks Allocation Scheme in Multi-UAV Context", Rapport LAAS No04741, 2004 International Conference on Robotics and Automation (ICRA'2004), New Orleans (USA), April 26 -   May 1  2004.

3.       Robert Zlot and Anthony Stentz, "Market-based Complex Task Allocation For Multirobot Teams", Army Science Conference, 2004.

 


Resources

Several useful hints about how to give a talk (by Bruce Donald)
Robotics on the web
Intelligent Systems Lab in Technion
Robohoo (Yahoo for robticsafficionados)
A sample of papers about Random Walks
Braitenberg-inspired lego-bots (video clip)