The focus of this work is on modeling the interaction dynamics of mobile robotic systems, i.e., modeling properties of the situated system that arise or evolve during execution as a result of the interaction between the robot(s) and the environment. In particular, we explore on-line modeling (i.e., modeling occurring within the lifetime of a task) in the stochastic and uncertain domain of physically embodied single-robot and multi-robot systems.

Our approach employs Augmented Markov Models (AMMs), a technique we have developed based on semi-Markov chains, but having additional statistics associated with links and nodes. We have developed an algorithm that constructs AMMs with little computational overhead, making it feasible for real-time applications (i.e., within the lifetime of a task). We have demonstrated AMMs in a number of robotics applications: fault detection, affiliation determination, hierarchy restructuring, regime detection, and reward maximization. The AMM-based evaluations used in these applications include statistical hypothesis tests and expectation calculations from Markov chain theory. Each of the applications is experimentally verified using up to four physical mobile robots performing elements of a foraging (collection) task.

The encompassing theme in this work is to provide pragmatic and theoretically sound, general-purpose tools for improving the performance of mobile robotic systems.

The goals of this project are:

1. To model on-line the interaction dynamics between a real-world robot and its environment.
2. To use the models in exploring applications not currently addressed in the literature.

• Each robot creates an Augmented Markov Model (AMM) during the execution of a task.
• The model states represent behaviors that the robot performs.
• The models capture the dynamics of controller execution in the robot's environment.

Augmented Markov Models (AMMs)
Augmented Markov Models are essentially probabilistic finite state machines augmented with statistics on link and node usage. In particular, an AMM is a subclass of semi-Markov chain. Our model construction algorithm is also able to capture the hidden state associated with second (and higher) order transitions. Below we describe the implementation of AMMs and the model construction algorithm. An AMM is a 5-tuple < S,A,B,L,T >

1. S, a set of symbols {s₁, s₂, . . . , s_M} recognized by the network.

2. A, a set of states (or nodes) {a₁, a₂, . . . , a_N}, each having four attributes:
   • a_i^s, the symbol recognized by the state.
   • a_i^m, average time steps spent in the state.
   • a_i^s2, variance associated with a_i^m.
   • a_i^p, probability of remaining in a_i in the next time step.

3. B, an N by M transition matrix, where b_i,k is the next state given a_i and s_k.

4. L, a set of directed links {l₁, l₂, . . . , l_P}, having six attributes:
   • l_i^f, state from which the link begins.
   • l_i^t, state to which the link connects.
   • l_i^d, number of times the link has been traversed.
   • l_i^S, total time spent in l_i^t, after first traversing the link.
   • l_i^S2, sum of squares of durations comprising l_i^S.
   • l_i^p, probability of using the link, given the system is in state l_i^f.

5. T, a set of elements {t₁, t₂, . . . , t_Q}, each storing data on a two-link transition entering and leaving a state, and having five attributes:
   • t_i^e, the link entering the state.
   • t_i^l, the link leaving the state.
   • t_i^d, the number of times t_i has been traversed.
   • t_i^S, total time steps spent in the state that t_i^l connects to, after first traversing t_i. t_i^S2, sum of squares of durations comprising t_i^S.

Characteristics of AMMs:

• Parsimonious.
• Computationally inexpensive to generate.
• Incrementally generated, allowing anytime use.
• Statistically-based node splitting reduces inconsistencies between training data and model.

Model use with mobile robots:
At each time step, the input symbol to the AMM uniquely represents a particular subset of the robot's active behaviors. AMM Construction Algorithm A stream of symbols belonging to S provides the data for model construction. Let sym be the current input symbol, oldsym the previous input symbol, and a_c the current state. For each input symbol do:

if sym == oldsym then
   remain in ac and update aip and the appropriate lS, lp, and tS 

else 
   if  sym is in S then
      S = S  unioned with {sym} 
      create a new state ai with ais = sym
      add the new transition to B

   endif
   create a link from ac to the new state if necessary
   create the two-link transition in T if necessary
   update acm, acs2, and ld, lS, lS2, lp, td, tS, tS2 as appropriate 
   do node-splitting if necessary
   transition to the new state
endif

Node-splitting:
For the current state, calculate the binomial mean and variance for transitions in T with the same in-link. If this mean is an outlier, then split the current state and attach the current in-link (with its associated out-links, as indicated in T) to the new state. Using T, make all probabilities consistent. Update T.

Experimental Task: Foraging

• Basic task: Robots search for pucks and bring them Home while avoiding obstacles and other robots.
• Dynamic leader selection: Robots are organized in a hierarchy with the most dominant being allowed to deliver its puck first.
• Regime detection: Robots first collect one color of puck then switch to another color when they determine the first is depleted.
• Reward Maximization: There are two colors of pucks, each with different reward values. When the robot finds a puck, it must determine if collecting it gives more reward or leaving it in search of a different color.

• Dani Goldberg and Maja J Mataric', (2000) "Maximizing Reward in a Non-Stationary Mobile Robot Environment," Submitted to Autonomous Agents and Multi-Agent Systems, special issue on the best of Agents 2000 (The Fourth International Conference on Autonomous Agents, Barcelona, Spain, June, 2000). [PDF]
• Dani Goldberg and Maja J Mataric', (2000) "Learning Multiple Models for Reward Maximization," Proceedings, The Seventeenth International Conference on Machine Learning (ICML-2000), Stanford University, June 29-July 2. [PDF]
• Dani Goldberg and Maja J Mataric', (2000) "Detecting Regime Changes with a Mobile Robot using Multiple Models," USC Institute for Robotics and Intelligent Systems Technical Report IRIS-00-382. [PDF]
• Dani Goldberg and Maja J Mataric', (2000) "Reward Maximization in a Non-Stationary Mobile Robot Environment," Proceedings, The Fourth International Conference on Autonomous Agents (Agents 2000), Barcelona, Spain, June 3-7. [PDF]
• Dani Goldberg and Maja J Mataric', (1999) "Mobile Robot Group Coordination Using a Model of Interaction Dynamics," Proceedings of the SPIE: Sensor Fusion and Decentralized Control in Robotic Systems II, Boston, Massachusetts, pp. 63-73.
• Dani Goldberg and Maja J Mataric', (1999) "Augmented Markov Models," USC Institute for Robotics and Intelligent Systems Technical Report IRIS-99-367. [PDF]
• Dani Goldberg and Maja J Mataric', (1999) "Coordinating Mobile Robot Group Behavior Using a Model of Interaction Dynamics," Proceedings, The Third International Conference on Autonomous Agents (Agents '99), Seattle, Washington, May 1-5. [PDF]

For more information contact Maja Mataric'.