bas2003 3870

Modeling Adaptive Robot Swarms: 

Modeling Adaptive Robot Swarms Kristina Lerman Aram Galstyan USC Information Sciences Institute Not an Inverse Problem

Why Analyze Adaptive Systems?: 

Why Analyze Adaptive Systems? To predict Behavior of the system under new conditions Aspects of the system not studied experimentally Large numbers of robots Dynamic environments To control Find parameters that optimize system performance Optimal number of robots for the task Find parameters that prevent instabilities, etc. To understand How individual robot characteristics affect collective behavior How system size affects performance of the system

Modeling and Analysis Tools: 

Modeling and Analysis Tools Microscopic (discrete) models describe/model individual robot’s behavior Equations of motion approach Explicitly account for all interactions Solve to obtain trajectories E.g., pheromone-based trail formation (Schweitzer et al., 1997) Microscopic simulations Abstract individual robot properties Probabilistic models (Martinoli et al., 1999) Robot’s actions modeled as series of stochastic events E.g., collaboration in robots (Ijspert et al., 2001) Others: cellular automata, molecular dynamics, etc.

Modeling and Analysis Tools (cont): 

Modeling and Analysis Tools (cont) Macroscopic (continuous) models describe collective behavior of groups of robots Finite difference equations Collaboration in robots (Martinoli & Easton, 2003) Synchronous Rate Equations Continuous limit of finite difference equations Alternatively, derived from Stochastic Master Equation Collaboration (Lerman et al., 2001) and foraging (Lerman & Galstyan, 2002) in robots Asynchronous

Rate Equations: 

Rate Equations We will use macroscopic models – Rate Equations – to study robots More computationally efficient than microscopic models Directly describe experimental observations Rate Equations describe average collective behavior, not a specific experiment describe results averaged over many experiments They are usually phenomenological Not derived from first principles Are easier to construct because you don’t have to explicitly model many individual details Microscopic details appear only in parameters of models Can be derived from stochastic microscopic description

What We Can Model Now: 

What We Can Model Now Types of robots modeled Reactive robots Perception and action are tightly coupled No memory or use of historical information Can use timers to trigger actions Adaptive robots Change their behavior in response to environmental changes or actions of other robots These are simple robots No intentionality No abstract representations Distributed system collective behavior arises out of local interactions among robots

Why Amenable to Analysis: 

Why Amenable to Analysis Individual robots can be modeled as stochastic processes Individual robot’s behavior subject to External forces may not be anticipated Noise fluctuations and random events Other robots with complex trajectories Can’t predict which robots will interact Errors in sensors and actuators Randomness programmed into controllers e.g., avoidance

Our Results: 

Our Results A framework for modeling collective behavior in reactive and adaptive robot systems Derived equations from theory of stochastic processes “Recipe” for creating application-specific models from individual robot controllers Models of distributed robot systems Collaborative stick-pulling Qualitative agreement with experimental/simulations results Analytic form for critical parameters Foraging Quantitative agreement with simulations results Optimal group size and its dependence on individual robot parameter Dynamic task allocation Individual robot transition rules for stable steady state distribution

Adaptation in Robot Swarms: 

Adaptation in Robot Swarms Adaptation is crucial for robotic swarms functioning in unstructured dynamic environments Adaptation allows robots to change their behavior in response to environmental changes or actions of other robots to improve the overall performance of the system

Memory as a Mechanism for Adaptation: 

Memory as a Mechanism for Adaptation Memory-based adaptation Robot makes observations; stores them in memory Uses observations to estimate the state of the environment and other robots Modifies its behavior accordingly Adaptive robots using memory of length m to make decisions about future actions can be represented as a generalized Markov process of order m

Adaptive Robots as Markov Processes: 

Adaptive Robots as Markov Processes Individual robot probability distribution p(n,t) = probability robot is in state n at time t Generalized Markov property: robot’s state at time t+Dt depends on its state at time t, and history of past m-1 states h={(n1,t), (n2,t-Dt),…, (nm,t-(m-1)Dt)} Change in probability density

Master Equation for Adaptive Systems: 

Master Equation for Adaptive Systems In the continuum limit, with transition rates Similar to the Stochastic Master Equation that describes evolution of physical systems

From One to Many: 

From One to Many Collective robot state If robots are independent and indistinguishable Collective configuration described by n={N1,…, NL} Nj = number of robots in state j P(n,t) = probability system is in configuration n at t Master Equation for P(n,t) specifies how the entire system evolves in time However, ME is often difficult to formulate and solve – it is difficult to define correct probability distribution for a system

Rate Equation: 

Rate Equation Instead, we work with the Rate Equation Derived from the Master Equation “First moment” of the ME Describes how the average number of robots in state k changes in time where <…>h denotes average over histories No need to know exact probability distributions Used in Ecology, Population Dynamics

Dynamic Task Allocation: 

Dynamic Task Allocation Task Robots are allocated to collect red or green pucks Goal Dynamically achieve an appropriate division of labor Mechanism Robot makes local observations and adds them to memory Each robot estimates the proportion of pucks and robots in the environment (from memory), and switches state accordingly Jones & Mataric

Modeling Adaptive Task Allocation: 

NR|G(t) number of robots in Red|Green state MR|G(t) number of Red|Green tasks aR|G(t,h) rate robots switch to Red|Green state bR|G rate robots complete Red|Green tasks mR|G rate at which new Red|Green tasks are added Modeling Adaptive Task Allocation

Transition Rates: 

Transition Rates Transition rates depend on nR,obs=NR,obs/(NR,obs+NG,obs) : observed density of Red robots mR,obs= MR,obs/(MR,obs+MG,obs) : observed density of Red pucks Mathematical form of transition rates Steady-state (SS): dnR/dt=0=aR nG-aGnR Desired SS solution: nR,SS= mR Intuitive guess: aR=f(nR-mR) Will lead to desired SS solution only when f(nR-mR)=0 Informed by analysis: aR=(1- mR)f(nR-mR) guarantees desired steady-state is satisfied non-trivially

Mathematical Form for f: 

Mathematical Form for f

Intuitive vs Informed Transition Rates : 

Intuitive vs Informed Transition Rates Simulations results with different transition rates Courtesy of C. Jones time aR=(1- mR)f(nR-mR) aR=f(nR-mR) Intuitive (power f ): Informed (power f ):

History and Transition Rates: 

History and Transition Rates t t-D … t-|h|D Robot’s memory

Time Delay Equations: 

Time Delay Equations Initial conditions

Dynamics of Red Robots: 

Dynamics of Red Robots Linear f Solutions show oscillations characteristic of delay equations Solutions eventually relax to puck distribution Magnitude of oscillations and relaxation time depend on size of history window

Solutions for Different f Same h: 

Solutions for Different f Same h

Slide24: 

Jones & Mataric

Conclusions: 

Conclusions Created a model of collective dynamics based on theory of stochastic processes Reactive robots Adaptive robots Applied formalism to distributed robotic systems Collaborative stick-pulling Foraging Dynamic task allocation Results Theoretical predictions agree at least qualitatively with results of experiments and simulations Analytic results not obtainable by other methods Insights into robot design (form for transition rates)

Future Work: 

Future Work Beyond the Rate Equation Take into account fluctuations Noisy observations Formulate and solve the collective Master Equation Appropriate form for probability distribution function for dynamic task allocation application More realistic models Don’t coarse-grain behaviors Automatic model construction Other systems – new challenges Self-reconfigurable robots Nano-robots

Roadmap to Theory: 

Roadmap to Theory Starting with an individual robot Derive stochastic Master Equation ME describes how robot’s state changes in time State=action or behavior the robot is executing Make transition to a multi-robot system Derive collective Master Equation describes how configuration of the system evolves in time ME is often difficult to formulate and solve Instead, work with the Rate Equation “Mean” or “First Moment” of the ME Practical “recipe” for constructing the Rate Equation from individual robot controller

Representation of Reactive Robots: 

Representation of Reactive Robots Finite state automata used to represent individual reactive robots (Arbib et al., 1981) State = behavior; transitions between states Example: simplified foraging diagram Collective behavior is captured by the same FSA Each robot in exactly one of finite number of states State = number of robots executing that behavior

Coarse-graining: 

Coarse-graining Coarse-graining reduces the complexity of the model Helps construct a minimal model that explains experiments

A “Recipe” for Rate Equations: 

A “Recipe” for Rate Equations Initial conditions: Ns(t=0)=N, Nh(0)=0, Np(0)=0

Transition Rates: 

Transition Rates Transition is triggered By a stimulus Obstacle, another robot in a particular state, location (e.g., home) By a timer Turn in a random direction for x seconds Calculating transition rates Calculated under assumptions Triggers are uniformly distributed in space Robots encounter triggers randomly Estimated from data by Calibration Run experiment or simulation for a single robot in an arbitrarily complex environment and measure relevant parameters Fitting Fit the model to the data