home

about

team

projects

papers

downloads

manual

messageboard

Hunter-Runner: Implementing HIVEMind on FlexBot

Aaron Khoo

HIVEMind

For papers describing the HIVEMind system as implemented on physical robot systems, please refer to my publications page.

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 99].

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.

Broadcast-based communication is not a novel idea on robots; some examples of implemented systems are:

  • The Alliance architecture [Parker 98].

  • [Goldberg and Mataric 00] presents several behavior-based multi-robot controllers used in a collection task.

  • [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:

  • kill-runner
    When all Hunters see the Runner, they open fire and kill the runner. 

  • unwedge 
    In case a runner is stuck on local scenery somewhere on the map

  • goto-xy 
    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 constant. 

  • stop

There are two top-level, serial, hand-crafted plans:

  • perform-hunt
    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.

  • goto-runner-position 
    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 Runner.

The Hunters shared five pieces of information between team members:

  • see-runner?
    Boolean value. Do I currently see the Runner? 

  • runner-trapped?
    Boolean value. Is the runner currently trapped?

  • source-node
    Integer value. What is the waypoint I last started out from?

  • dest-node
    Integer value. What is the waypoint I am going to?

  • current-level
    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. 

References 

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

  khoo@cs.northwestern.edu