Autonomy Oriented Computing

AOC
Autonomy Oriented Computing - From Problem Solving to Complex Systems Modeling
Authors: Liu, Jiming, Jin, XiaoLong, Tsui, Kwok Ching
Publisher: Springer
2005, XXXII, 216 p., 57 illus., Hardcover
ISBN: 1-4020-8121-9
For retail information, please visit Springer Online
Poster of AOC
Slides of AOC Book (6.17 MB) [New]

Introduction

With the advent of computing, we are fast entering a new era of discovery and opportunity. In business, market researchers will be able to predict the potential market share of a new product on-the-fly by synthesizing news reports, competitor analysis, and large-scale simulations of consumer behavior. In life and material sciences, specially engineered amorphous computational particles will be able to perform optimal search, whether they are bio-robot agents to kill cancer cells inside human bodies or smart paints to spread evenly over and fill cracks on rugged surfaces. In environmental sciences, surveillance applications will be able to deploy wireless, mobile sensor networks to monitor wild vegetation and route the tracking measurements of moving objects back to home stations efficiently and safely. In robotics, teams of rescue or Mars exploratory robots will be able to coordinate their manipulation tasks in order to collectively accomplish their missions, while making the best use of their capabilities and resources.

All the above examples exhibit a common characteristic, that is, the task of computing is seamlessly carried out in a variety of physical embodiments. There is no single multi-purpose or dedicated machine that can manage to accomplish a job of this nature. The key to success in such applications lies in a large-scale deployment of computational agents capable of autonomously making their localized decisions and achieving their collective goals.

We are now experiencing a world in which the traditional sense of computers is getting obsolete. It calls for a more powerful, intelligent computing paradigm for handling large-scale data exploration and information processing. We are in a critical moment to develop such a new computing paradigm in order to invent new technologies, to operate new business models, to discover new scientific laws, and even to better understand the universe in which we live.

In human civilizations, science and technology develop as a result of our curiosity to uncover such fundamental puzzles as who we are, how the universe evolves, and how nature works, multiplied by our desires to tackle such practical issues as how to overcome our limitations, how to make the best use of our resources, and how to sustain our well-being.

This book is a testimony of how we embrace new scientific and technological development in the world of computing. We specifically examine the metaphors of autonomy as offered by nature and identify their roles in addressing our practical computing needs. In so doing, we witness the emergence of a new computing paradigm, called autonomy oriented computing (AOC).

While existing methods for modeling autonomy are successful to some extent, a generic model or framework for handling problems in complex systems, such as ecological, social, economical, mathematical, physical, and natural systems, effectively is still absent. Autonomy oriented computing (AOC) unifies the methodologies for effective analysis, modeling, and simulation of the characteristics of complex systems. In so doing, AOC offers a new computing paradigm that makes use of autonomous entities in solving computational problems and in modeling complex systems. This new paradigm can be classified and studied according to (1) how much human involvement is necessary and (2) how sophisticated a model of computational autonomy is, as follows:

AOC-by-fabrication: Earlier examples with this approach are entity-based image feature extraction, artificial creature animation, and ant colony optimization. Lifelike behavior and emergent intelligence are exhibited in such systems by means of fabricating and operating autonomous entities.

AOC-by-prototyping: This approach attempts to understand self-organized complex phenomena by modeling and simulating autonomous entities. Examples include studies on Web regularities based on self-adaptive information foraging entities.

AOC-by-self-discovery: This approach automatically fine-tunes the parameters of autonomous behaviors in solving and modeling certain problems. A typical example is using autonomous entities to adaptively solve a large-scale, distributed optimization problem in real time.

As compared to other paradigms, such as centralized computation and top-down systems modeling, AOC has been found to be extremely appealing in the following aspects:

To capture the essence of autonomy in natural and artificial systems;
To solve computationally hard problems, e.g., large-scale computation, distributed constraint satisfaction, and decentralized optimization, that are dynamically evolving and highly complex in terms of interaction and dimensionality;
To characterize complex phenomena or emergent behavior in natural and artificial systems that involve a large number of self-organizing, interacting entities;
To discover laws and mechanisms underlying complex phenomena or emergent behaviors.

Early Work on AOC

The ideas, formulations, and case studies that we introduce in this book have resulted largely from the research undertaken in the AOC Research Lab of Hong Kong Baptist University under the direction of Professor Jiming Liu. In what follows, we highlight some of the earlier activities in our journey towards the development of AOC as a new paradigm for computing.

Our first systematic study on AOC originated in 1996. As originally referred to Autonomy Oriented Computation, the notion of AOC first appeared in the book of Autonomous Agents and Multi-Agent Systems (AAMAS). Later, as an effort to promote the AOC research, the First International Workshop on AOC was organized and held in Montreal in 2001.

Earlier projects at the AOC Lab have been trying to explore and demonstrate the effective use of AOC in a variety of domains, covering constraint satisfaction problem solving, mathematical programming, image processing. Since 2000, projects have been launched to study the AOC approaches to characterizing (i.e., modeling and explaining) observed or desired regularities in real-world complex systems, e.g., self-organized Web regularities and HIV infection dynamics, as a white-box alternative to the traditional top-down or statistical modeling.

These AOC projects differ from traditional AI and agent studies in that here we pay special attention to the role of self-organization, a powerful methodology as demonstrated in nature and well suited to the problems that involve large-scale, distributed, locally interacting, and sometimes rational entities. This very emphasis on self-organization was also apparent in the earlier work on collective problem solving with a group of autonomous robots.

Recently, we have started to explore a new frontier, the AOC applications to the Internet. This work has dealt with the theories and techniques essential for the next paradigm shift in the World Wide Web, i.e., the Wisdom Web. It covers a number of key Web Intelligence (WI) capabilities, such as (1) autonomous service planning; (2) distributed resource discovery and optimization; (3) Problem Solver Markup Language (PSML); (4) social network evolution; (5) ubiquitous intelligence.

Overview of the Book

This book is intended to highlight the important theoretical and practical issues in AOC, with both methodologies and experimental cases studies. It can serve as a comprehensive reference book for researchers, scientists, engineers, and professionals in the fields of computer science, autonomous systems, robotics, artificial life, biology, psychology, ecology, physics, business, economics, and complex adaptive systems, among others.

It can also be used as a text or supplementary book for graduate or undergraduate students in a broad range of disciplines, such as:

Agent-Based Problem Solving;
Amorphous Computing;
Artificial Intelligence;
Autonomous Agents and Multi-Agent Systems;
Complex Adaptive Systems;
Computational Biology;
Computational Finance and Economics;
Data Fusion and Exploration;
Emergent Computation;
Image Processing and Computer Vision;
Intelligent Systems;
Modeling and Simulation;
Nature Inspired Computation;
Operations Research;
Optimization;
Programming Paradigms;
Robotics and Automation;
Self-Organization.

The book contains two parts. In Part I, Fundamentals, we describe the basic concepts, characteristics, and approaches of AOC. We further discuss the important design and engineering issues in developing an AOC system, and present a formal framework for AOC modeling. In Part II, AOC in Depth, we provide detailed methodologies and case studies on how to implement and evaluate AOC in problem solving (i.e., Chapter 5, AOC in Constraint Satisfaction and Chapter 7, AOC in Optimization) as well as in complex systems modeling (i.e., Chapter 6, AOC in Complex Systems Modeling). In these chapters, we start with introductory or survey sections on practical problems and applications that call for the respective AOC approach(es) and specific formulations. In Chapter 8, Challenges and Opportunities, we revisit the important ingredients in the AOC paradigm and outline some directions for future research and development.

The book contains numerous illustrative examples and experimental case studies. In addition, it also includes exercises at the end of each chapter. These materials further consolidate the theories and methodologies through:

Solving, proving, or testing some specific issues and properties, which are mentioned in the chapter;
Application of certain methodologies, formulations, and algorithms described in the chapter to tackle specific problems or scenarios;
Development of new formulations and algorithms following the basic ideas and approaches presented;
Comparative studies to empirically appreciate the differences between a specific AOC method or approach and other conventional ones;
Philosophical and critical discussions;
Survey of some literature and hence identification of AOC research problems in a new domain.

Whether you are interested in applying the AOC techniques introduced here to solve your specific problems or you are keen on further research in this exciting field, we hope that you will find this thorough and unified treatment of AOC useful and insightful. Enjoy!

Table of Contents

Part I - Fundamentals

Chapter 1 − From Autonomy to AOC

1.1 Introduction

1.2 Basic Concepts and Taxonomies

1.3 General AOC Approaches

1.4 AOC as a New Computing Paradigm

1.5 Related Areas

1.6 Summary

Chapter 2 − AOC at a Glance

2.1 Introduction

2.2 Autonomy Oriented Problem Solving

2.3 Autonomy Oriented Search

2.4 Autonomy Oriented Learning

2.5 Summary

Chapter 3 − Design and Engineering Issues

3.1 Introduction

3.2 Functional Modules in an Autonomous Entity

3.3 Major Phases in Developing AOC Systems

3.4 Engineering Issues

3.5 Features and Characteristics of AOC Systems

3.6 Performance Considerations

3.7 Simulation Environments

3.8 Summary

Chapter 4 − A Formal Framework of AOC

4.1 Introduction

4.2 Elements of an AOC System

4.3 Interactions in an AOC System

4.4 Remarks on Homogeneity, Heterogeneity, Hierarchy of Entities

4.5 Self-Organization in AOC

4.6 Summary

Part II - AOC in Depth

Chapter 5 − AOC in Constraint Satisfaction

5.1 Introduction

5.2 Background

5.3 ERE Model

5.4 An Illustrative Example

5.5 Experimentation

5.6 Discussion

5.7 Entity Network for Complexity Analysis

5.8 Summary

Chapter 6 − AOC in Complex Systems Modeling

6.1 Introduction

6.2 Background

6.3 Autonomy Oriented Regularity Characterization

6.4 Experimentation

6.5 Discussions

6.6 Summary

Chapter 7 − AOC in Optimization

7.1 Introduction

7.2 Background

7.3 EDO Model

7.4 Benchmark Optimization Problems

7.5 Performance of EDO

7.6 Experimentation

7.7 Discussions

7.8 Summary

Chapter 8 − Challenges and Opportunities

8.1 Lessons Learned

8.2 Theoretical Challenges

8.3 Practical Challenges

8.4 Summary

Selected Publications

Copyright Notice: The copyright of each downloadable publication on this web site is retained by authors or other copyright holders. All persons copying the downloadable publications should adhere to the terms and constraints invoked by each author or pulisher's copyright. These publications should not be reposted without the explicit permission from the copyright holders.

In the following, the publications are inverse-chronologically ordered:

2005

Jiming Liu, Xiaolong Jin, and Kwok Ching Tsui, Autonomy Oriented Computing (AOC): Formulating Computational Systems with Autonomous Components, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans (in press); [PDF]
Jiming Liu, Xiaolong Jin, and Yuanshi Wang, Agent-Based Load Balancing on Homogeneous Minigrids: Macroscopic Modeling and Characterization, IEEE Transactions on Parallel and Distributed Systems (in Press). [PDF]

2004

Jiming Liu, Shiwu Zhang, and Jie Yang, Characterizing Web Usage Regularities with Information Foraging Agents, IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 4, pp. 566-584, 2004. [PDF] [Software]

2003

Jiming Liu, Web Intelligence (WI): What Makes Wisdom Web? in Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, Aug. 9-15, 2003, pp. 1596-1601, Morgan Kaufmann Publishers;
Jiming Liu, Web Intelligence (WI): Some Research Challenges, Invited Talk, the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, Aug. 9-15, 2003;
Yuanshi Wang and Jiming Liu, Macroscopic Model of Agent Based Load Balancing on Grids, in Proceedings of the Second International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'03), Melbourne, Australia, Jul. 14-18, 2003;
Kwok Cing Tsui, Jiming Liu, and M. J. Kaiser, Self-Organized Load Balancing in Proxy Servers, Journal of Intelligent Information Systems, Kluwer Academic Publishers, Vol. 20, No. 1, pp. 31-50, 2003.

2002

Jiming Liu, Han Jing, and Y. Y. Tang, Multi-Agent Oriented Constraint Satisfaction, Artificial Intelligence, Vol. 136 , No. 1, pp. 101-144, 2002; [PDF]
Jiming Liu and Yi Zhao, On Adaptive Agentlets for Distributed Divide-and-Conquer: A Dynamical Systems Approach, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, Vol. 32, No. 2, pp. 214-227, 2002;
Jiming Liu, Xiaolong Jin, and Jing Han, A Self-Organizing Approach to Solving Constraint Satisfaction and Satisfiability Problems, International Journal of Pattern Recognition and Artificial Intelligence, Vol. 16, No. 8, pp. 1041-1064, 2002; [Software]
Xiaolong Jin and Jiming Liu, Multiagent SAT (MASSAT): Autonomous Pattern Search in Constrained Domains, in Proceedings of the Third International Conference on Intelligent Data Engineering and Automated Learning (IDEAL'02), Hujun Yin et. al. Eds., pp. 318-328, Manchester, UK, Aug. 2002; [Software]
Kwok Ching Tsui and Jiming Liu, Evolutionary Multi-agent Diffusion Approach to Optimization, International Journal on Pattern Recognition and Artificial Intelligence, Vol. 16, No. 6, pp. 715-733, 2002; [PS] [Software]
Kwok Ching Tsui and Jiming Liu, Evolutionary Diffusion Optimization, Part I: Description of the Algorithm, in Proceedings of the 2002 Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii, May 12-17, 2002; [Software]
Kwok Ching Tsui and Jiming Liu, Evolutionary Diffusion Optimization, Part II: Performance Assessment, in Proceedings of the 2002 Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii, May 12-17, 2002; [Software]
Jiming Liu and Hong Qin, Behavioral Self-Organization in Synthetic Agents, Autonomous Agents and Multi-Agent Systems, Kluwer Academic Publishers, Vol. 5, No. 4, pp. 397-428, 2002.

2001

Jiming Liu and Jianbing Wu, Multi-Agent Robotic Systems, CRC Press, 2001;
Jiming Liu, Autonomous Agents and Multi-Agent Systems: Explorations in Learning, Self-Organization, and Adaptive Computation, World Scientific Publishing, 2001;
Jiming Liu, Kwok Ching Tsui, and Jianbing Wu, Introducing Autonomy Oriented Computation (AOC), in Proceedings of the First International Workshop on Autonomy Oriented Computation (AOC 2001), pp. 1-11, Montreal, May, 2001.

2000

Jiming Liu and Jian Yin, Multi-Agent Integer Programming. In Lecture Notes in Computer Science, Vol. 1983, Springer, pp. 301-307, 2000.

1999

Jing Han, Jiming Liu, and Q. Cai, From ALife Agents to a Kingdom of N Queens, in Jiming Liu and Ning Zhong, editors, Intelligent Agent Technology: Systems, Methodologies, and Tools, World Scientific Publishing, pp. 110-120, 1999;
Jiming Liu and Jianbing Wu, Evolutionary Group Robots for Collective World Modeling, in Proceedings of the Third International Conference on Autonomous Agents (AGENTS'99), Seattle, WA, May 1-5, 1999;

1997

Jiming Liu, Y. Y. Tang, and Y. Cao, An Evolutionary Autonomous Agents Approach to Image Feature Extraction, IEEE Transactions on Evolutionary Computation, Vol. 1, No. 2, pp. 141-158, 1997; [PDF]
Jiming Liu, Hong Qin, Y. Y. Tang, and Y. Wu, Adaptation and Learning in Animated Creatures, in Proceedings of the First International Conference on Autonomous Agents (AGENTS'97), Marina del Rey, California, Feb. 5-8, 1997.

In the following, the publications are ordered according to their topics:

AOC in General

Jiming Liu, Xiaolong Jin, and Kwok Ching Tsui, Autonomy Oriented Computing (AOC): Formulating Computational Systems with Autonomous Components, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans (in press); [PDF]
Jiming Liu, Autonomous Agents and Multi-Agent Systems: Explorations in Learning, Self-Organization, and Adaptive Computation, World Scientific Publishing, 2001;
Jiming Liu, Kwok Ching Tsui, and Jianbing Wu, Introducing Autonomy Oriented Computation (AOC), in Proceedings of the First International Workshop on Autonomy Oriented Computation (AOC 2001), pp. 1-11, Montreal, May, 2001;
Jiming Liu and Jianbing Wu, Multi-Agent Robotic Systems, CRC Press, 2001;

Web Regularity Characterization

Jiming Liu, Shiwu Zhang, and Jie Yang, Characterizing Web Usage Regularities with Information Foraging Agents, IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 4, pp. 566-584, 2004. [PDF] [Software]

AOC Based CSP Solver: ERA

Jiming Liu, Han Jing, and Y. Y. Tang, Multi-Agent Oriented Constraint Satisfaction, Artificial Intelligence, Vol. 136 , No. 1, pp. 101-144, 2002; [PDF]
Jing Han, Jiming Liu, and Q. Cai, From ALife Agents to a Kingdom of N Queens, in Jiming Liu and Ning Zhong, editors, Intelligent Agent Technology: Systems, Methodologies, and Tools, World Scientific Publishing, pp. 110-120, 1999.

AOC Based SAT Solver: MASSAT

Jiming Liu, Xiaolong Jin, and Jing Han, A Self-Organizing Approach to Solving Constraint Satisfaction and Satisfiability Problems, International Journal of Pattern Recognition and Artificial Intelligence, Vol. 16, No. 8, pp. 1041-1064, 2002; [Software]
Xiaolong Jin and Jiming Liu, Multiagent SAT (MASSAT): Autonomous Pattern Search in Constrained Domains, in Proceedings of the Third International Conference on Intelligent Data Engineering and Automated Learning (IDEAL'02), Hujun Yin et. al. Eds., pp. 318-328, Manchester, UK, Aug. 2002; [Software]

AOC Based Optimizer: EDO

Kwok Ching Tsui and Jiming Liu, Evolutionary Multi-agent Diffusion Approach to Optimization, International Journal on Pattern Recognition and Artificial Intelligence, Vol. 16, No. 6, pp. 715-733, 2002; [PS] [Software]
Kwok Ching Tsui and Jiming Liu, Evolutionary Diffusion Optimization, Part I: Description of the Algorithm, in Proceedings of the 2002 Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii, May 12-17, 2002; [Software]
Kwok Ching Tsui and Jiming Liu, Evolutionary Diffusion Optimization, Part II: Performance Assessment, in Proceedings of the 2002 Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii, May 12-17, 2002. [Software]

Web Intelligence (WI)

Jiming Liu, Web Intelligence (WI): What Makes Wisdom Web? in Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, Aug. 9-15, 2003, pp. 1596-1601, Morgan Kaufmann Publishers;
Jiming Liu, Web Intelligence (WI): Some Research Challenges, Invited Talk, the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, Aug. 9-15, 2003;

Image Processing and Feature Extraction

Jiming Liu and Yi Zhao, On Adaptive Agentlets for Distributed Divide-and-Conquer: A Dynamical Systems Approach, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, Vol. 32, No. 2, pp. 214-227, 2002;
Jiming Liu, Y. Y. Tang, and Y. Cao, An Evolutionary Autonomous Agents Approach to Image Feature Extraction, IEEE Transactions on Evolutionary Computation, Vol. 1, No. 2, pp. 141-158, 1997. [PDF]

Load Balancing

Jiming Liu, Xiaolong Jin, and Yuanshi Wang, Agent-Based Load Balancing on Homogeneous Minigrids: Macroscopic Modeling and Characterization, IEEE Transactions on Parallel and Distributed Systems (in Press); [PDF]
Kwok Cing Tsui, Jiming Liu, and M. J. Kaiser, Self-Organized Load Balancing in Proxy Servers, Journal of Intelligent Information Systems, Kluwer Academic Publishers, Vol. 20, No. 1, pp. 31-50, 2003;
Yuanshi Wang and Jiming Liu, Macroscopic Model of Agent Based Load Balancing on Grids, in Proceedings of the Second International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2003), Melbourne, Australia, Jul. 14-18, 2003.

Behavioral Self-Organization

Jiming Liu and Hong Qin, Behavioral Self-Organization in Synthetic Agents, Autonomous Agents and Multi-Agent Systems, Kluwer Academic Publishers, Vol. 5, No. 4, pp. 397-428, 2002;
Jiming Liu and Jianbing Wu, Evolutionary Group Robots for Collective World Modeling, in Proceedings of the Third International Conference on Autonomous Agents (AGENTS'99), Seattle, WA, May 1-5, 1999;
Jiming Liu, Hong Qin, Y. Y. Tang, and Y. Wu, Adaptation and Learning in Animated Creatures, in Proceedings of the First International Conference on Autonomous Agents (AGENTS'97), Marina del Rey, California, Feb. 5-8, 1997.

Mathematical Programming

Jiming Liu and Jian Yin, Multi-Agent Integer Programming. In Lecture Notes in Computer Science, Vol. 1983, Springer, pp. 301-307, 2000.