Hunter-Runner: Implementing HIVEMind on FlexBot
For papers describing the
HIVEMind system as implemented on physical robot systems, please refer
to my publications
Our bots are written using a
behavior-based approach that obeys circuit semantics (see our
papers for more details on this). Essentially this means that our
control programs resemble feed-forward circuits. "Behaviors"
tightly connect sensors to actuators and are calculated ostensibly in
parallel with each other; on a serial machine, the behaviors are
actually compiled into straight line code through the GRL compiler [Horswill
From this point, it is possible
to construct a communication mechanism where "virtual wires"
connect appropriate parts of the control programs on different bots. On
physical robots, these virtual wires are simulated through the use of a
broadcast mechanism such as User Datagram Protocol (UDP). On our
half-life bots, which are assumed to be all co-located on the same
physical machine, the wires are easily implemented through the use of
shared global variables. All relevant information (essentially the
entire knowledgebase for the robot) is shared with all other team
members through this communication mechanism, leading to a shared
situational awareness, or HIVEMind.
is not a novel idea on robots; some examples of implemented systems are:
architecture [Parker 98].
[Goldberg and Mataric 00]
presents several behavior-based multi-robot controllers used in a
[Balch and Arkin 98]
describe a schema system that maintains military formations such as
a line, wedge, diamond or column.
Our HIVEMind implementation on
physical robots extends traditional behavior-based systems (which are
propositional in nature) by implementing quantified inference
over unary predicates. However, for the Hunter-Runner task described
here, we just utilized the simpler propositional structure without the
more powerful representations.
The figure above is not meant
to be a complete representation of a Hunter's control program. It is
just a partial view demonstrating the wires within a single bot, and the
virtual wires connecting two bots. In the above case, the sensor runner-trapped?
is a boolean passed between the two bots and OR'ed together. The
resultant output is passed to perform-hunt and goto-runner,
which in turn control the goto-xy behavior.
Hunters utilize four behaviors:
When all Hunters see the Runner, they open fire and kill the
In case a runner is stuck on local scenery somewhere on the map
Go to a specific xy location on a map. The Hunters navigate using a
set of waypoints. Instead of using A*, we simply pre-calculate paths
between all possible waypoints. Then we store these paths in a
look-up table. So, when a bot arrives at waypoint A, and wishes to
travel to waypoint B, then it simply looks up the table to find
waypoint C (the next waypoint to go to. The table is n-squared in
the number of total waypoints on the map, but look-up time is
There are two top-level,
serial, hand-crafted plans:
This executes the search algorithm as described on the previous
page. It terminates when at least one Hunter senses that the Runner
has been trapped.
This plan is executed when the team knows the Runner is trapped
somewhere. Each Hunter then makes its own way to the location of the
The Hunters shared five pieces
of information between team members:
Boolean value. Do I currently see the Runner?
Boolean value. Is the runner currently trapped?
Integer value. What is the waypoint I last started out from?
Integer value. What is the waypoint I am going to?
Integer value. This integer indicates what level of the graph we
are currently at. The Hunters coordinate movement based on this
value. When a Hunter reaches its destination, it increments its
current-level value and waits until all other Hunters have the same
value before continuing onto the next step of the search.
T. Balch and R.C. Arkin(1998) Behavior-based
formation control for multirobot teams, IEEE Transactions on
Robotics and Automation, vol. 14, no. 6, pp. 926--939, December 1998.
D. Goldberg and M.J.
Mataric(2000) Robust Behavior-Based Control for Distributed
Multi-Robot Collection Tasks, USC Institute for Robotics and
Intelligent Systems Technical Report IRIS-00-387
I. Horswill(1999). Functional
programming of behavior-based systems. In Proc. IEEE International
Symposium on Computational Intelligence in Robotics and Automation
L.E. Parker(1998) ALLIANCE:
An Architecture for Fault Tolerant Multirobot Cooperation, IEEE
Transactions on Robotics and Automation, Vol. 14, No. 2, April 1998.
The Search Algorithm | Movies