InterJournal Complex Systems, 1106
Status: Accepted
Manuscript Number: [1106]
Submission Date: 2004
The Ecological Ideal Free Distribution and Resource Allocation in Distributed Computing and Control: Theory and Cross-Fertilization for Applications
Author(s): Jorge Finke ,Kevin M. Passino

Subject(s): CX.3

Category:

Abstract:

The ideal free distribution (IFD) concept from ecology characterizes how animals optimally distribute themselves across habitats. The word "ideal" refers to the assumption that animals have perfect sensing capabilities for determining habitat quality. "Free" indicates that they can move from any habitat directly to any other habitat at any time. If an animal perceives one habitat as "better," via some correlate of fitness such as rate of arrival of nutrients, it will move to it. This movement will, however, reduce its new habitat's desirability, both to itself and other animals at that habitat. The IFD is the equilibrium distribution where all animals achieve equal fitness. Suppose that in a distributed computing system there are spatially-distributed computing "nodes" that are interconnected by a computer network, and a continuous input of tasks to the nodes that need to be processed. Suppose that there are task-processing "software agents" that can move about the network and seek to allocate their processing services to nodes in order to optimize the overall task processing rate for the distributed computing system. This can occur via distributed "resource allocation" algorithms for moving software agents around the network to respond to task-processing demands. In this paper we first establish an analogy where we view both animals and software agents as generic agents, nutrients as tasks, and habitats as nodes. The computer network topology can represent which other nodes (habitats) an agent can sense at each node (i.e., "perceptual constraints"), and travel constraints that dictate which nodes (habitats) can be traveled to from a given node (habitat). Network delays can represent agent movement constraints (e.g., agent velocity limits coupled with inter-habitat distances). We specify a mathematical "discrete event system model" of the generic problem by generalizing models of the "load balancing problem" in distributed computing. We show how an "invariant set" can represent the IFD, and generalizations of it that result when the "ideal" and "free" assumptions are lifted. We then use Lyapunov stability analysis of this invariant set to illustrate that there is a wide class of agent strategies (i.e., "proximate" decision-making mechanisms), and resulting agent movement trajectories across nodes (habitats), that still achieve the desired distribution. The results extend the existing theory of the IFD by showing the impact of a class of perceptual constraints, travel constraints, movement trajectories, and animal strategies on achievement of the distribution. Next, we will show via simulations how the ideas apply to cooperative control of a network of autonomous vehicles when vehicles must be allocated to spatially-distributed tasks.

Retrieve Manuscript
Submit referee report/comment


Public Comments: