About AOC AOC Group Publications Software Resources Forum

Home >> AOC Group >> AOC Group Projects
AOC Group Projects

This page contains descriptions of the projects that have been completed by the 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

  • J Liu, KC Tsui and J Wu, Introducing Autonomy Oriented Computation, in Proceedings of First International Workshop on Autonomy Oriented Computation, pp. 1-11, 2001.
  • J Liu and KC Tsui, Autonomy Oriented Computation, Technical Report COMP-03-003, Department of Computer Science, Hong Kong Baptist University.

^ 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

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

Publications

Web user surfing behavior characterization

  • J Liu, SW Zhang and Y Ye, Understanding emergent WWW regularities with information foraging agents, in Proceedings of the 1st International Joint Conference on Autonomous Agents and Multi-agent Systems (AAMAS 2002), Bologna, Italy, pp. 457-458, July 15-19, 2002
  • J Liu and SW Zhang, Unveiling the origins of Internet use patterns, in Proceedings of INET 2001, The Internet Global Summit, Stockholmsm?ssan, Stockholm, Sweden, June 5-8, 2001.
  • J Liu and SW Zhang, Characterizing Web Usage Regularities with Information Foraging Agents, accepted by IEEE Transactions on Knowledge and Data Engineering, 2003 (in press).
  • J Liu, SW Zhang and Y Ye, Agent-based Characterization of Web Regularities, in N Zhong, J Liu and Y Yao (eds), Web Intelligence, chapter 2, pp. 19-36, Springer-Verlag, 2003 (in press).
  • J Liu and SW Zhang, Multi-Phase Sumo Maneuver Learning, accepted by Robotica (in press), 2003.
  • J Liu and SW Zhang, Multi-Phase Genetic Programming: A Case Study in Sumo Maneuver Evolution, accepted by International Journal of Pattern Recognition and Artificial Intelligence, 2003 (in press).

HIV dynamics characterization

^ top

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

  • J Liu, XL Jin, J Han, A Self-Organizing Approach to Solving Constraint Satisfaction and Satisfiability Problems, International Journal of Pattern Recognition and Artificial Intelligence, Vol. 16, No. 8 (2002), pp. 1041-1064.
  • XL Jin, J Liu, Multiagent SAT (MASSAT): Autonomous Pattern Search in Constrained Domains, in Proceedings of the Third International Conference on Intelligent Data Engineering and Automated Learning (IDEAL2002), Hujun Yin et. al. Eds., pp. 318-328, Manchester, UK, August 2002.
  • Y Tang, J Liu and XL Jin , Adaptive Compromises in Distributed Problem Solving, in Proceedings of The Fourth International Conference on Intelligent Data Engineering and Automated Learning (IDEAL'03), Hong Kong, China, March, 2003.

^ 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

^ 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

^ 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

^ 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

^ top

From Local Interactions to Global Behaviors in a Multi-Agent RoboNBA Game

Multi-Agent System (MAS) is a very challenging research topic. In many systems, the interaction between agents often lead to global level, nonlinear behaviors, which are not easily predicted only from the behaviors of individual agents.

We use RoboNBA as a platform, where two teams of autonomous robots (agents) can play basketball with each other. It has a server and two clients. At each cycle, the server is responsible for receiving and executing commands from clients as well as sending sensor information to clients. Clients receive sensor information from the server, interpret it and calculate relevant commands based on sensor information. Then clients will send commands to the server for the next cycle execution.

We have been investigating the following two properties of the RoboNBA:

  • How local interaction can influence the global performance of RoboNBA. Particularly, how the strategies of clients have an impact on the global performance of RoboNBA.
  • How local interaction can affect the global behaviors of the RoboNBA. For example, under what condition RoboNBA will exhibit complex or interesting behaviors? How do we measure these complex or interesting behaviors?

Publications

^ top

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:

  • Profile and Index Grid service descriptions
  • Search and Discover Grid services
  • Generate and Coordinate service flow upon user requests

Publications

^ top

Demo Projects

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

Semantic Web Planning

Project Link

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.

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

Basketball Strategy Simulation System

Project Link

In the project, a distributed multi-agent system called Basketball Strategy Simulation System (BSSS) was developed for simulating the strategies in a basketball competition. In the real world, strategies selected inside the basketball game are decided by the coach. Although the result of the ball game and the basketball players' performance are difficult to estimate, it is feasible for us to simulate the ball game result using a multi-agent system.

Each basketball player is first simulated for their abilities. The abilities of those simulated basketball players are gathered from the statistics on the NBA official website. For those players who have good performance statistics, their corresponding simulated players will have higher  ability values. The rules of the simulated ball games are pre-defined and different kinds of rules will be triggered according to the players' ability parameters.

Consequently, the simulation can illustrate graphically the animated basketball game. After the simulation is completed, the result of the ball game and the basketball players' performance are shown.

RoboCup Simulation System

Project URL

RoboCup Simulator is a software platform in which two teams of autonomous agents (11 players per team) can perform a RoboCup football match. As in a real match, each agent detects various situations in the dynamically changing, competitive and cooperative environment, and selects its reactive behavior and maneuvers, accordingly.

In this project, we show how the cooperation among team members of different strategy settings affects the match results.

^ top