Page 443 - Sensing, Intelligence, Motion : How Robots and Humans Move in an Unstructured World

418 SUGGESTED COURSE PROJECTS

Suggested course topics can be roughly divided into three categories: theory
and algorithms; computer simulation; experimental (hardware) work. A project
may fall into more than one category; for example, one may be assigned to
develop an algorithm and validate it by theoretical analysis and a computer sim-
ulation. Examples of topics in each category are given below.

Theory and Algorithms for Sensor-Based Motion Planning

1. Sensor-based motion planning for multiple mobile robots:
• Centralized motion planning: All or most commands to all robots come
from one center.
• Decentralized motion planning: Each robot makes its motion planning
decisions on its own, without coordinating it with other robots. Various
options can be considered here, for example: A robot knows nothing
about other robots’ decisions except by watching them move; or, robots
may distribute their next step decisions to other robots; or, in a given
pair of robots, one is required to report its planning decisions to the other
but not vice versa. A mathematically interesting problem is an inter-
ception problem: One robot tries to escape from a robot that attempts
to intercept it; different assumptions about sensing means, speeds, and
knowledge about the other robot abilities gives rise to different schemes.
• Collective behavior of multiple robots. Again, different behavioristic
schemes addressing motion planning can be considered here, such as
making and changing formations, covering a maximum area (the Mush-
room Pickers problem), etc.
• Motion planning for tethered robots. Such problems appear in some
industrial settings—for example, a Robot World system where tethered
robots are floating above an assembly table (a two-dimensional setting);
or underwater robot probes connected by tethers to the mother ship (a
three-dimensional setting). Options include the tether being able, or not
being able, to sense surrounding objects or other robots and tethers.
One may want to consult related literature.
• Computational geometry: efficient (static or dynamic) division of work
space between a few robots (such as when vacuum cleaning a super-
market floor); the rendezvous problem for two robots. The performance
criteria may include minimizing the total path (equivalent to minimiz-
ing energy), or minimizing total time spent on the job, or minimizing
wasted walks over areas that have been cleaned already or walks to
charging stations.
2. Hierarchical motion planning systems: combining prior knowledge (e.g.,
a map of the area) with on-line sensor data. For example, inspection of a
nuclear plant after a major disaster: Some areas may be still as they were
before the event, and some may be damaged by an explosion, so the robot
must be able to deviate from the map using its sensing and intelligence.