This page contains descriptions of the projects that actively pursued by members of the AAMAS/AOC group.  The projects are:

Autonomy Oriented Computing

Nature is full of complex systems that exhibit intelligent behavior and they have been studied extensively from different angles and with different objectives. Some researchers want to understand the working mechanism of the complex system concerned. Immunologists, for example, want to know the way human immune system reacts to antigens. Similarly, economists want to know the factors contributing to the ups and downs in share prices. The knowledge gained in this way helps the scientists to predict future system behavior. Other researchers studying complex system behavior want to simulate the observed complex behavior and formulate problem solving strategies for hard computational problems such as global optimization. Computer scientists and mathematicians have formulated various algorithms based on natural evolution for solving their problems at hand. In general, one wants to be able to explain, predict, reconstruct and deploy a complex system.

Common techniques for complex systems modeling can broadly be divided into top-down and bottom-up approaches. Top-down approaches start from the high-level system and use various techniques such as ordinary differential equations. These methods generally treat every part of a complex system homogeneously and tend to model the average case well, where regional variation in behavior is minimal and can be ignored. However, it seems this is not always applicable. Bottom-up approaches, on the other hand, start from the smallest and simplest elements of the system.  Models are built based on the observation that  entities in a complex system are autonomous, emergent, adaptive and self-organized.

We propose autonomy oriented computing (AOC) as a new paradigm for solving hard computational problems and for characterizing the behaviors of a complex system. The first goal of AOC is to reproduce life-like behavior in computation. With detailed knowledge of the underlying mechanism, simplified life-like behavior can be used as model for a general-purpose problem solving technique. Replication of behavior is not the end, but rather the means, of these computational algorithms. The second goal of AOC is to understand the underlying mechanism of a real-world complex system by hypothesizing and repeated experimentation. The end product of these simulations is a better understanding of or explanations to the real working mechanism of the modeled system. The third goal of AOC concerns the emergence of a problem solver in the absence of human intervention. In other words, self-adaptive algorithms are desired.

Topics that we are interested in includes, but are not limited to, the following areas:

1. Methodology, Theory and Perspectives of AOC. Measurement of emergence; measurement of evolvability; self-organization in complex systems; behavior monitoring of autonomous societies; performance measurement for AOC-based systems; formation of roles and social structure in the communities; embodiment of autonomous entities; and dialectics of microscopic and macroscopic autonomies.

2. Implementation Issues. Guidelines for designing AOC; simulating environments and languages for AOC; architectural issues; tractability and scalability of algorithms; visualization of activities in the testing environments; and the design of local and global interaction rules.

3. Applications. Examples of successful application of AOC to real-life problems; potential application areas of AOC (e.g. distributed search, financial market modeling, data analysis).

4. Comparisons. Strength and weaknesses of AOC vs. other multiagent paradigms such as evolutionary computation, multiagent simulation, emergent computation, artificial life, L-systems, evolutionary strategies, cellular automata; and empirical performance comparison using benchmark problems.

Publications:

Back to Top

Multi-Agent Systems and Agent Networks

When using a multi-agent based approach to solve a problem, agents will implicitly or explicitly form relationships of cooperations or coordinations. An agent network is a virtual network where nodes are agents and edges are relationships among them. In this project, we aim at studying the following issues:

1. What is the relationship between the representation of the given problem and the topology of the resulting agent network? 

2. If the topology of an agent network varies according to specific problem representations, how does it reflect the computational complexity of the given problem?

In one study, we examined two multi-agent based representations of SATs and further experimentally studied the topologies of the resulting agent networks. We showed that different representations of the agent networks will manifest different topologies, notably a small-world. Generally speaking, a small-world topology will computationally harden a search process. Therefore, we proposed a guiding principle for designing a search problem solver by a multi-agent system, i.e. one should avoid having small-worlds among agents and intra- and inter- agent computational complexity should be balanced.

Publications:

Back to Top

Multi-agent Based Simulation of Complex Adaptive Systems

A complex adaptive system (CAS ) involves numerous entities that interact with each other. A CAS often exhibits emergent behaviors that are not predefined and are adaptive to changes in the environment. Examples of CAS in the real world include economy, ecology, weather system, motor traffic, human society, culture and immune system.

Our objective is to model, understand and predict behaviors in a CAS in the real world via a bottom-up agent based simulation approach. Two sub-projects have been completed.

Web user surfing behavior characterization

Publications:

HIV dynamics characterization

Back to Top

A Distributed Approach to Solving SAT Problems

Many problems, both practical (e.g., classes scheduling in a school, electronic circuit design) and theoretical (e.g., coloring problem), can be formulated into SAT problems that  determine whether a (propositional) formula has at least one solution. It is the first problem proven to be NP-complete. And it has the simplest representation among all NP-complete problems. As a result, SAT has attracted significant attention from many research communities.

General methods to solve SAT problems can be classified into two types: complete and incomplete. Complete methods basically are derived from DPLL procedure. For any given SAT problem, complete methods can prove whether a SAT problem is satisfiable or unsatisfiable. In spite of their completeness, they are very slow. Incomplete methods, on the other hand, are based on the concept of Local Search. Compared to complete methods, incomplete methods are faster. But they cannot prove the unsatisfiability of a given problem. Therefore, there is no guarantee of finding a solution to a SAT problem.

Both DPLL procedure and Local Search methods are, in essence, sequential. Therefore, they are quite slow in solving a given problem. In order to overcome such a drawback, we propose in this project a distributed multi-agent based approach, namely, MASSAT to solve SAT problems. In our approach, propositional variables are divided into several groups, and each variable group is represented by an agent. The search space specified by the given problem is regarded as an environment where agents live. To solve the problem, agents will move guided by some reactive rules in their environment until a solution state emerges or a time bound is reached. A solution state, if emerged, is obtained by combining the positions of all agents.

Publications:

Back to Top

Evolutionary Diffusion Optimization

Nature-inspired stochastic search methods such as evolutionary algorithms and simulated annealing have been successfully applied to many global optimization tasks.  This project attempts to formulate a stochastic population-based search method based on some observations from diffusion in nature.  For example, human movement follows certain tract empowered either by a small step movement or by the availability of information passed over by others who have migrated already.  Similarly, the movement of dust particles in the air is Brownian and the random move is a special case of it.

Evolutionary Diffusion Optimization (EDO) attempts to capture the 'trend' of the search landscape and share this information between agents belonging to the same family.  Meanwhile, members of the same family perform the local search by diffusion based on the shared 'trend' and provide feedback to the parent regarding the usefulness of the 'trend'.  Successful agents will also become parents and inherit the 'trend' information from their parents, which will subsequently be updated by their own offspring agents.

 The major differences between EDO and many nature-inspired search algorithms include: (1) variable population size; (2) inclusion of random move as a diffusion operator; (3) selection for reproduction by local competition; (4) adaptive search step size; (5) minimal use of global information. Experimental results show that EDO is able to maintain a good balance between exploration and exploitation while performing automatic search step size adaptation at the same time.  Hence, EDO belongs to the aoc-by-self-exploration class within the AOC framework.  The first application of EDO is function optimization and we are working on the well-known combinatorial optimization task of (symmetric) traveling salesmen problem.

Publications:

Back to Top

Adaptive Distributed Caching

It is well-known that the Internet is growing everyday, both in terms of the number of new web pages being put online and the amount of traffic.  The common way to shorten the latency of Web object delivery is by caching frequently requested object and can be implemented both on the server side and the client side.  It is often the case that a proxy server is installed in large organizations so that work load can be shared between them.  The main questions to ask then become: What is the best policy to distribute the load and what happens if the proxy server infrastructure changes.

The common way to tackle the above problems is by pre-assignment using a hash function.  It should work well if the hardware is functional all the time and there is no need to add more resources to the proxy system. The objective of this project is to tackle the above two problems by a self-organizing system.  In other words, we want to make the proxy server system to be autonomic - to 'learn' the best way to distribute the workload, to degrade gracefully in the wake of hardware failure, and to react appropriately when new resources become online.  We achieve this by modeling each proxy as an autonomous entity and allowing them to make their own decisions.  In particular, we allow them to decide whether to cache an object and whether a client request should be passed onto another proxy or the original server.  We call these schemes selective caching and request forwarding.

Publications:

Back to Top

Self-Organized Load Balancing on Grids

In recent years, there is an explosion of interest in the study of agent-based grid computing. The interest is originally motivated by large-scale scientific computing, where the use of supercomputers is often not practicable. A number of less powerful computers on networks maybe used to replace such supercomputers. Agent-based grid computing is the technology capable of exploiting and operating such distributed computers. After the workload is divided into a large number of independent tasks, the challenge in grid computing lies in load balancing.

The network of computers lacks fixed structures as its nodes come and go freely. Therefore the master-slave structure , where a centralized master disperses computing tasks to slaves, is not applicable to grid computing. Peer to peer (P2P) systems  are introduced to model the microscopic behaviors of agent-based load balancing. In P2P systems, all nodes are homogeneous peers and their control is completely  decentralized.  In  the P2P paradigm, load balancing is fulfilled by a large number of relatively simple autonomous agents and each task is carried by a 'mobile' agent. Here 'mobile' means the agent is active and free to choose nodes.

Microscopic simulations model the interactions between individual agents and give empirical understanding of  load balancing behaviors. However, they offer only an empirical and indirect method of studying load balancing. Macroscopic models, where the number and size of teams at nodes are considered and the difference between individual agents is ignored, can give a direct description about the load balancing behaviors. Since there are only a few parameters, some important properties of the macroscopic models can be given by using mathematical tools. For example, some parameters can be proven to be important to the global behaviors of the whole system.

Publications:

Back to Top

Coordination Strategies for Team-based Intelligent Agents in Competitive Multi-agent Systems

In different multi-agent applications, agents coordinate in different fashions. In a team-based competitive game, agents coordinate to enhance their collective performance in winning the game. RoboCup, based on the soccer game, is a fully distributed, multi-agent system. It provides a standard platform for testing a number of AI technologies, such as multi-agent collaboration, real-time reasoning and planning, intelligent robotic designing, etc. In our project, we use RoboCup as a typical competitive environment to test the effectiveness and efficiency of multiple strategies, which are helpful for dynamically decision-making process of each player..

An interesting research problem in team-based games is the role assignment problem. The problem requires agents to decide what roles they should take based on some real-time feedbacks from a dynamically changing environment. The Minority Game (MG), as widely used in modeling financial marketing problems, has shown very similar characteristics that meet the fundamental requirements of the role assignment problem. In MG, agents are not interacted locally, self-organization is embodied by the feedback from collective behaviors. MG is a theory to study the cooperation and competition of agents given limited resources. In MG, players get the experience by adjusting the scores of their equipped strategies.

In the current step of our project, we propose a formulation of MG strategies for studying the role assignment problem in a particular multi-agent system: RobotCup Simulation League (RSL). Through experiments, we demonstrate that MG strategies improve the effectiveness of the role assignment among agents in a real competitive environment. The improvement validates some characteristics as discovered in the theoretical MG model

Publications:

Autonomous Grid Service Composition

Grid is an infrastructure that enables resource sharing and coordinated problem solving in dynamic and distributed Virtual Organizations (VOs). Embracing Web services on Grid has recently been realized, which opens up the service-oriented computing paradigm to be applied in Grid. Thus, the need for composing and orchestrating resource-conscious Grid services follows immediately.

Our Objective is to develop a Problem Solving Environment (PSE) that can autonomously:

Demo Projects

Some of the software demo projects centered around the research themes of the group.  A partial list of the projects is:

The Semantic Web extends the current state of the Web with well-defined meaning. The idea is to define markup for the contents of the Web in a way that software agents can interpret. This will enable the exchange and sharing of information throughout the Web.

In this project, a planning agent that interprets the planning information from the Semantic Web documents were developed. The meaning and relation of the information in these documents were specified by ontologies. These ontologies were defined using DARPA Agent Markup Language (DAML). The agent is a general-purpose planner that uses a Partial-Order Planning (POP) algorithm to search throughout the space of plans to find the solutions.

A consultation system for a computer store has been developed to show the capabilities of the Semantic Web planning agent. The customers can consult on what hardware configurations can satisfy their requirements. Hardware properties for each company are described in the Semantic Web documents. All of these documents are distributed on the Internet. The use of POP can make sure that all the hardware components are compatible with each other. To increase the efficiency of the consultation system, a Case-Based Reasoning (CBR) algorithm was also used to reuse knowledge in the old cases from the case base.

---

All rights reserved.
For problems or questions regarding this web contact the webmaster.
Last updated: 11.18.2003.