Ruling Distributed Dynamic Worlds / Edition 1 available in Hardcover
- ISBN-10:
- 0471655759
- ISBN-13:
- 9780471655756
- Pub. Date:
- 05/27/2005
- Publisher:
- Wiley
Hardcover
Buy New
$159.95Buy Used
$102.47-
-
SHIP THIS ITEM
Temporarily Out of Stock Online
Please check back later for updated availability.
-
Overview
Product Details
| ISBN-13: | 9780471655756 |
|---|---|
| Publisher: | Wiley |
| Publication date: | 05/27/2005 |
| Series: | Wiley Series on Parallel and Distributed Computing , #59 |
| Pages: | 288 |
| Product dimensions: | 6.40(w) x 9.50(h) x 0.70(d) |
About the Author
Read an Excerpt
Ruling Distributed Dynamic Worlds
By Peter Sapaty
John Wiley & Sons
ISBN: 0-471-65575-9Chapter One
INTRODUCTION
We start with naming some exemplary areas that need radically new ideologies and technologies aimed at efficient organization of large distributed systems, explaining the existing problems of their understanding and management. Introductory ideas and simple practical examples explaining the essence of WAVE-WP (or World Processing), a novel technology that can rule a variety of distributed artificial and natural systems on a high, semantic level, are presented and discussed. Comparison with the predecessor model WAVE revealed in a previous book (Sapaty, 1999a), as well as the relation to other works in the area, is given, and the general organization of the book is outlined.
1.1 TOWARD COORDINATION AND MANAGEMENT OF LARGE SYSTEMS
1.1.1 Shifting from Computation to Coordination
The use of computers is steadily shifting from computations to coordination and management of complex distributed and dynamic systems, in both civil and military areas. Removing consequences of earthquakes and flooding, recovery after terrorist attacks, or joint military operations in the world's hot spots are examples where distributed computerized systems may be particularly useful and efficient.
Both national and international campaigns of the scale and complexity never seen before may need to be planned, simulated, and managed, often within severe timeconstraints. These campaigns may use simultaneously within one system many human, technical, and natural resources distributed over large territories.
Radically new integration and coordination models and technologies may help such systems operate efficiently and fulfill their objectives, as traditional ones, stemming, say, from the Turing machine (Herken, 1995; Turing, 1936) or cellular automata (Wolfram, 1994) and oriented on computations, are becoming a real bottleneck.
1.1.2 Overoperability Versus Interoperability
Many current works in the field of integration and simulation of large systems orient on the support of interoperability between system components, where any unit can plug into a computer and see the same picture, say, of a battlefield. It is not easy to do, however, and billions of dollars are being spent on interoperability problems (Erwin, 2002).
This, however, may not be sufficient for the real integration, nor may be needed in general (Sapaty, 2002). For example, a tank driver should operate and make individual decisions within her direct vision only, and a local commander, executing orders from above, has to know the region where troops subordinate to her operate, rather than the whole battlefield.
The common picture is logically (not always practically, however) the simplest way to glue together unstructured or poorly organized systems. It reminds us, in some sense, the first multiprocessor computers which were designed decades ago. They were based on a common memory box, as the first feasible solution. In highly dynamic systems like real or symbolic battlefields, the huge amount of information they possess is an integral and inseparable part of the processes there. Making this information available for many players means that we must regularly create its snapshots and distribute them among the participants.
This may require highly intensive communications and broadband channels, which in severe and hostile environments may become a painful bottleneck. Also, as the information in such systems is changing with great speed, any snapshot of it may potentially be useless and "dead." And for security reasons, especially in military applications, the global system picture may need to be hidden rather than commonly available and shared.
Real integration may be based on more rational system principles, where parts are not necessarily equal to share the common picture (or do not share it at all, in the usual sense). They may rather form altogether a highly organized whole that defines the role of its parts and their interactions and not the other way round. The system's parts may lose their identity within such an organization, with their main goal being to satisfy the whole rather than evolve and prosper themselves.
Usually, such higher level organizations are a prerogative of human intelligence and manned command-and-control infrastructures. But emerging new types of distributed systems, especially those using automated and unmanned platforms and oriented on solving dynamic tasks in unpredictable environments, may require shifting of an essential part of this "overoperability" to the efficient automatic level.
Traditional agent-based philosophies and approaches (Earnshaw and Vince, 2002; Bigus et al., 2001; Lange and Oshima, 1998; Milojicic et al., 1999; Siegwart et al., 2004; Wooldridge, 2002), first designing parts and then assembling the whole from these parts in the hope it works properly, may not be able to cope with large dynamic systems, and higher level organizational models and technologies, directly supporting the system whole and guaranteeing the needed global behavior, are of growing importance.
1.1.3 Intelligent Systems Versus Intelligent Components
Theoretically, many jobs in dynamic environments can be performed by teams of robots better than by individual robots (Gage, 1993). And, technologically, any number of sophisticated mobile robots can be produced by industry today. But we are still far away from any suitable team solutions that could allow us to use this abundant and cheaper hardware efficiently, as the teamwork is a complex and insufficiently studied phenomenon, with neither universal nor even suitable results proposed so far.
A considerable increase in the robot's individual and group intelligence at the current stage may, however, be achieved by raising the level of language with which robots, especially their teams, are programmed and tasked. This can be used subsequently as a qualitatively new platform for the creation of advanced robotic systems that may integrate different existing control approaches or may be based on radically new, higher level organizational models.
We already have such precedents. Only with the introduction of high-level programming languages such as FORTRAN or LISP did real and massive use (as well as production) of computers began. It became possible to express the semantics of problems directly, abstracting from hardware details and drastically improving application programming productivity, with the system intelligence shifting from computer system components to programming languages and the quality of their implementation.
We can pursue a similar approach for multirobot systems, considering them not as a collection of intelligent individuals (which may never reach human- or even animal-like level), but rather as a parallel machine capable of executing any mission tasks written in a universal high-level scenario language (Sapaty, 2001a). Its automatic implementation, which may be environment dependent and emergent, can be effectively delegated to the distributed artificial brain embedded in, and formed by, multiple robots, as shown in Figure 1.1.
Having designed such a language, we now have the possibility of programming and organizing highly intelligent distributed systems as a whole, rather than assembling them from self-contained intelligent elements, which may be lost indiscriminately, say, on a battlefield, putting at risk the whole system. The needed system intelligence may always be kept in the mission scenario regardless of the run time composition of a system executing this scenario, thus enabling us to fulfill the mission objectives under any circumstances.
1.1.4 Directly Operating in Physical World
We also need models that can describe much broader activities than traditional information processing, enabling us to operate in real worlds directly, with physical movement and physical matter and object transference and manipulation.
Let us consider some examples of doing jobs in a physical world that may hint at how world-processing models and languages can be organized. For instance, if we want to perform a job, we first find a proper place, say, by a landmark or deviation from the current place (a hill at the right, 600 meters northwest, etc.), then move there with operations (machinery or equipment), and data, which may comprise both information and physical matter (a written plan of the job and, say, sand, bricks, water, ammunition, etc.).
Having performed the job (building a house, firing ammunition) using the data brought and/or existing there (say, left by other works), we may leave new data and the changes in the environment (the house built), pick up other data (unused materials), and move to other points, together with other operations (fresh or released equipment), to do another job (building a new house or a bridge), and so on. We may also need to bring results back to some point to be analyzed and processed (sand or water collected remotely, weapons or information seized in a reconnaissance operation, soil samples returned by a rover to a lander) to do other jobs or move further in case of success or failure.
Many jobs can be done simultaneously in the same or in different locations in the physical world. In performing jobs, we may cooperate or compete with others, seeing where, what, and how they do (moving in a chain, e.g., needs leveling and keeping distance with neighbors). Moving and doing jobs may depend on results and states reached in other places (deployment of a combat group only after success of another group, or entire mission abortion if the headquarters has been destroyed). Global control over evolving jobs may coexist with autonomous decision making.
To make real progress in this direction, we may need the design of a universal model, language and technology that would allow for an efficient description and implementation of a variety of parallel activities in a distributed physical world, similar to those sketched above.
1.1.5 Distributed Artificial Life
Life on Earth is a collective rather than individual phenomenon. It is also a distributed one. Different biological species can survive only if they communicate, and there are enough of them, being efficiently spread over vast territories. Artificial life approach (Langton, 1997; Ward, 2000) is so far considered mostly the creation and reproduction of individual life and single robotic species.
It is the right time to investigate a higher level now where distributed artificial systems and multiple robots can be really useful and can evolve if applied massively and work cooperatively. New advanced approaches for describing distributed autonomous systems on much higher levels than usual may be needed.
This may allow us to comprehend the very sense and basic evolution mechanisms of artificial life on a semantic level and also find, for instance, the critical robotic mass for this life to exist and prosper, using for simulation both single and parallel computers as well as computer networks.
The areas listed above are only a few of many where the design, or even invention, of radically new system creation and management models and technologies, like the one described in this book, are of highest interest and importance at present.
1.2 PROBLEMS OF MANAGING LARGE DISTRIBUTED SYSTEMS
Single-machine solutions often exhibit highest possible integrity as a system, with all resources at hand, and control being global, direct and absolute. On the contrary, the creation and management of large distributed systems that should behave as a single controllable entity pursuing global goals and recovering from damages can meet serious difficulties. Let us explain why.
1.2.1 From Localized to Distributed Solutions
In Figure 1.2 a symbolic splitting of the single-machine functionality into pieces for their distribution is shown, which may be based on separating by operations, separating by data, or by both.
The resultant local functionalities may need to exist in more than a single copy in the distributed system (i.e., they should be replicated and spread throughout the space rather than localized and shared) for performance optimization, say, to become closer and work directly with other parts, and also to operate simultaneously with each other.
To work together as a distributed system, the parts of Figure 1.2b may need scores of other things to be additionally set up and integrated with them. First of all, there should be communication and synchronization, allowing them to exchange data via the data channels, to be established too. Second, the parts should have between (and over) them a sort of command-and-control (CC) infrastructure, to provide both local and global coordination and the ability to pursue common goals and obey global instructions. Within this infrastructure, additional control centers may be needed along with special control channels between them, and the control network may be multilayered for complex systems.
We have mentioned only a few additional things to be set up over the basic, split into pieces, functionality to work as a system, but even these can make the distributed solution very complex, as shown symbolically in Figure 1.3. Many other organizational tools and their interactions may be needed for this distributed system to operate properly (like, e.g., a recovery system, which may be distributed too and deeply integrated with both local functionalities and the distributed control).
1.2.2 More Distribution Problems and Details
Distributed Algorithms May Differ. The other difficulties may be in that the distributed algorithms may differ essentially from the centralized sequential ones (in our case of Fig. 1.2a), and they may need updating if not full rewriting of the functional parts shown in Figure 1.2b (as well as, possibly, introduction of other parts) to operate in a distributed and parallel manner. To bring the organization of Figure 1.3 to life, we may need to use together quite different existing languages and tools, and the whole system may become hugely overwhelmed with seams, scars, patches, and multiple interfaces.
Working in the Real World. In the real world, these functional pieces may have to acquire bodies and move physically, access and process not only information but physical matter or physical objects as well, also exchange the matter with each other along with the information, and so on. Additional control nodes and their communications with the original functional units and between them may require special (possibly, mobile) hardware units dedicated to command and control in the physical word.
Overwhelming Overhead. Creation, understanding, debugging, and subsequent managing of such distributed and dynamic systems may become a very complex problem, with the complexity growing drastically with the scale of problems to be solved. The organizational overhead, shown in Figure1.3, may considerably overwhelm the useful functionality of integral localized solutions, as in Figure 1.2a.
Starting from Scratch for Each Problem. And for each new problem (at least for each class of them), the whole work of creating, assembling, and debugging the complex distributed organization of Figure 1.3 must be repeated, possibly, from scratch. This is because the local functions and their interactions, also the needed control over them, may be unique for each problem to be solved.
Other Philosophies Needed. For solving complex problems in real, especially unpredictable and hostile, environments, we may need distributed systems organized in a very different manner than described above, with much higher clarity, flexibility, and also capability to recover after damages. This may require inventing, prototyping, and testing of quite different organizational ideologies, methodologies, and technologies than usual, as well as a possible revision of the ruling philosophies of existence, evolution, and general behavior of large dynamic and open systems, both manned and unmanned.
1.3 WAVE-WP: BASIC IDEAS
WAVE-WP is a completely different paradigm than any existing approaches oriented on distributed computation, coordination, and control. We provide here a sketch of some of its basic ideas and features.
1.3.1 The Whole First
Any existing approaches to investigation and management of large systems are analytical in nature, that is, first breaking the system into self-contained pieces or agents (or creating them from the start), studying them in detail, and then trying to assemble from these pieces the system as a whole, seeing this whole from the level of these pieces.
(Continues...)
Excerpted from Ruling Distributed Dynamic Worlds by Peter Sapaty Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
Preface.1. INTRODUCTION.
1.1 Toward Coordination and Management of Large Systems.
1.2 Problems of Managing Large Distributed Systems.
1.3 WAVE-WP: Basic Ideas.
1.4 Example: The Shortest Path Problem.
1.5 Example: Distributed Knowledge Representation and Processing.
1.6 System organization as a function of the application scenario.
1.7 Relation to the Previous Book.
1.8 Comparison with Other Works in Related Areas.
1.9 Organization of the Book.
2. WORLDS AND WAVES IN THE WAVE-WP MODEL.
2.1 Physical World.
2.2 Virtual World.
2.3 United Physical–Virtual World.
2.4 Execution World.
2.5 Waves.
2.6 Conclusions.
3. WORLD PROCESSING LANGUAGE.
3.1 Top Language Organization.
3.2 Data Definitions.
3.2.1 General on Constants.
3.2.2 Special Constants.
3.2.3 Vectors.
3.3 Variables.
3.4 Acts.
3.5 Rules.
3.6 Forward Rules.
3.7 Echo Rules.
3.8 Expressions.
3.9 Working with Physical Matter.
3.10 Conclusions.
4. DISTRIBUTED WAVE-WP INTERPRETATION IN DYNAMIC ENVIRONMENTS.
4.1 Doers and Their Networks.
4.2 Wave-WP Interpreter Architecture.
4.3 Track Infrastructure.
4.4 Elementary Operations Involving Multiple Doers.
4.5 More Complex Spatial Operations.
4.6 Other Distributed Interpretation Issues.
4.7 Conclusions.
5. SPATIAL PROGRAMMING IN WAVE-WP.
5.1 Traditional Sequential and Parallel Programming.
5.2 Virtual World Programming.
5.3 Mobility of Doers in Physical World.
5.4 Moving and Acting in Physical World Directly.
5.5 Programming in Integration of Physical and Virtual Worlds.
5.6 Conclusions.
6. EXEMPLARY MISSION SCENARIOS.
6.1 Coordinated Movement of a Group.
6.2 Physical Matter Delivery and Remote Processing.
6.3 Physical World Search Assisted by Virtual World.
6.4 Map-Based Collection of Samples.
6.5 Conclusions.
7. DISTRIBUTED MANAGEMENT USING DYNAMIC INFRASTRUCTURES.
7.1 Distributed Creation and Reconfiguration of an Infrastructure.
7.2 Dynamic Hierarchy Based on Physical Neighborhood.
7.3 Basic Command-and-Control Scenario in WAVE-WP.
7.4 Solving Distributed Management Problems.
7.5 Air Traffic Management in Dynamic Environments.
7.6 Conclusions.
8. MORE CRISIS MANAGEMENT SCENARIOS AND SYSTEMS.
8.1 Region Patrol by Mobile Robots.
8.2 Distributed Dynamic Cognitive Systems.
8.3 Multirobot Hospital Scenarios.
8.4 Future Combat Systems.
8.5 Crises Management in Open Networks.
8.6 Using Global Infrastructures in WAVE-WP.
8.7 Conclusions.
9. CONCLUSIONS.
9.1 Summary of the Main Features of WAVE-WP.
9.2 Some Main Application Areas.
9.3 Final Remarks.
9.4 Future Plans.
APPENDIX: WAVE-WP SUMMARY.
A.1 Extended Language Syntax.
A.2 Compact Syntax Description.
A.3 Permitted Abbreviations.
References.
Index.