Ruling Distributed Dynamic Worlds

by Sapaty, Peter

• ISBN13: 9780471655756
• ISBN10: 0471655759
• Edition: 1st
• Format: Hardcover
• Copyright: 2005-05-27
• Publisher: Wiley-Interscience

Summary

A sequel to Mobile Processing in Distributed and Open Environments, this title introduces an extended, universal WAVE-WP model for distributed processing and control in dynamic and open worlds of any natures. The new control theory and technology introduced in the book can be widely used for the design and implementation of many distributed control systems, such as intelligent network management for the Internet, mobile cooperative robots, Rapid Reaction forces, future Combat Systems, robotics and AI, NMD, space research on other planets, and other applications. This title: Demonstrates a much simpler and more efficient application programming Cultivates a new kind of thinking about how large dynamic systems should be designed, organized, tasked, simulated, and controlled Introduces an extended, universal WAVE-WP model for distributed processing Compares the universal WAVE-WP model to other existing systems used in intelligent networking

Author Biography

PETER S. SAPATY, PhD, is Director of Distributed Simulation and Control, Institute of Mathematical Machines and Systems, National Academy of Sciences of Ukraine. He also worked in Germany, UK, Canada, and Japan as project leader and research professor, and is currently a visiting professor at the University of Aizu in Japan.

Table of Contents

Preface	xv
1 INTRODUCTION	1	(32)
1.1 Toward Coordination and Management of Large Systems	1	(4)
1.1.1 Shifting from Computation to Coordination	1	(1)
1.1.2 Overoperability Versus Interoperability	2	(1)
1.1.3 Intelligent Systems Versus Intelligent Components	3	(1)
1.1.4 Directly Operating in Physical World	4	(1)
1.1.5 Distributed Artificial Life	5	(1)
1.2 Problems of Managing Large Distributed Systems	5	(3)
1.2.1 From Localized to Distributed Solutions	5	(1)
1.2.2 More Distribution Problems and Details	6	(2)
1.3 WAVE-WP: Basic Ideas	8	(2)
1.3.1 The Whole First	8	(1)
1.3.2 WAVE-WP Spatial Automaton	9	(1)
1.3.3 Implementation Basics	9	(1)
1.4 Example: The Shortest Path Problem	10	(11)
1.4.1 Importance of Distributed and Parallel Solutions	11	(1)
1.4.2 Finding Shortest Path Tree	11	(2)
1.4.3 Collecting the Shortest Path Between Nodes	13	(2)
1.4.4 Main Problems of Distributed Implementation	15	(1)
1.4.5 Universal WAVE-WP Interpreters	16	(1)
1.4.6 Shortest Path Tree Finding in WAVE-WP	17	(2)
1.4.7 Shortest Path Collection in WAVE-WP	19	(1)
1.4.8 Full Program for Finding Shortest Path	20	(1)
1.5 Example: Distributed Knowledge Representation and Processing	21	(5)
1.5.1 Knowledge Network	21	(1)
1.5.2 Elementary Query 1	22	(2)
1.5.3 Elementary Query 2	24	(2)
1.6 System organization as a function of the application scenario	26	(1)
1.7 Relation to the Previous Book	26	(1)
1.8 Comparison with Other Works in Related Areas	27	(3)
1.8.1 Parallel Computing	27	(1)
1.8.2 Distributed Systems and Distributed Computing	27	(1)
1.8.3 Parallel and Distributed Computing	28	(1)
1.8.4 Computer Networking	28	(1)
1.8.5 Intelligent Agents	28	(1)
1.8.6 Mobile Agents	28	(1)
1.8.7 Grid Computing	29	(1)
1.8.8 Spatial Programming	29	(1)
1.8.9 Mobile Robotics, Cooperative Robotics	29	(1)
1.8.10 System Management	29	(1)
1.9 Organization of the Book	30	(3)
2 WORLDS AND WAVES IN THE WAVE-WP MODEL	33	(26)
2.1 Physical World	34	(4)
2.1.1 Temporary Physical World Nodes	34	(1)
2.1.2 Visiting Existing Nodes in a Region	35	(1)
2.1.3 Destination Regions for New Nodes	36	(1)
2.1.4 Accessing Physical World Parameters	36	(1)
2.1.5 Broadcasting in Physical World	37	(1)
2.2 Virtual World	38	(4)
2.2.1 Knowledge Networks	38	(1)
2.2.2 Access to Nodes and Links	39	(1)
2.2.3 Tunnel and Surface Broadcasting	40	(1)
2.2.4 Linking with Alien Networks	41	(1)
2.3 United Physical-Virtual World	42	(2)
2.3.1 The Integration Details	42	(1)
2.3.2 Access to Nodes in the United World	43	(1)
2.3.3 United World Dynamics	44	(1)
2.3.4 Time and Speed	44	(1)
2.4 Execution World	44	(3)
2.4.1 Doers and Their Connections	45	(1)
2.4.2 Distribution of Physical-Virtual World Between Doers	46	(1)
2.4.3 Absolute and Mapping Addresses	47	(1)
2.4.4 Further Integration of Physical-Virtual-Execution World	47	(1)
2.5 Waves	47	(9)
2.5.1 Nature of Waves	47	(2)
2.5.2 Navigation in Space	49	(1)
2.5.3 Actions in Nodes	49	(1)
2.5.4 Coverage with Rules	50	(1)
2.5.5 Composition and Structuring of Waves	50	(3)
2.5.6 Wave Expressions and Remote Data	53	(2)
2.5.7 Delivery and Processing of Physical Matter	55	(1)
2.6 Conclusions	56	(3)
3 WORLD PROCESSING LANGUAGE	59	(40)
3.1 Top Language Organization	60	(2)
3.2 Data Definitions	62	(4)
3.2.1 General on Constants	62	(1)
3.2.2 Special Constants	63	(3)
3.2.3 Vectors	66	(1)
3.3 Variables	66	(7)
3.3.1 Nodal Variables	67	(1)
3.3.2 Frontal Variables	67	(1)
3.3.3 Environmental Variables	68	(5)
3.4 Acts	73	(12)
3.4.1 Flow Acts	74	(7)
3.4.2 Fusion Acts	81	(4)
3.5 Rules	85	(1)
3.5.1 Rules in General	85	(1)
3.5.2 State Generalization Procedure	85	(1)
3.6 Forward Rules	86	(7)
3.6.1 Branching Rules	86	(3)
3.6.2 Repetition	89	(1)
3.6.3 Synchronization	90	(1)
3.6.4 Protecting Common Resources	90	(1)
3.6.5 Network Creation	91	(1)
3.6.6 Autonomy Rules	92	(1)
3.7 Echo Rules	93	(2)
3.8 Expressions	95	(1)
3.9 Working with Physical Matter	96	(1)
3.10 Conclusions	97	(2)
4 DISTRIBUTED WAVE-WP INTERPRETATION IN DYNAMIC ENVIRONMENTS	99	(24)
4.1 Doers and Their Networks	99	(2)
4.2 Wave-WP Interpreter Architecture	101	(5)
4.2.1 Main Interpreter Components	101	(3)
4.2.2 Exemplary Interpretation Patterns	104	(1)
4.2.3 Integration of the Interpreter with Other Systems	105	(1)
4.3 Track Infrastructure	106	(3)
4.3.1 Forward and Backward Operations	106	(1)
4.3.2 Optimization of the Track Network	107	(2)
4.4 Elementary Operations Involving Multiple Doers	109	(6)
4.4.1 Local Operations in Doers	109	(2)
4.4.2 Creating a New Virtual Node in Another Doer	111	(2)
4.4.3 Moving into a New Physical Location	113	(2)
4.5 More Complex Spatial Operations	115	(3)
4.5.1 Moving Data Through Tracks	116	(1)
4.5.2 Migration of Knowledge Networks Between Doers	117	(1)
4.6 Other Distributed Interpretation Issues	118	(3)
4.6.1 Mapping Strategies	118	(1)
4.6.2 Dealing with Shortage of Vehicles	118	(3)
4.7 Conclusions	121	(2)
5 SPATIAL PROGRAMMING IN WAVE-WP	123	(34)
5.1 Traditional Sequential and Parallel Programming	123	(7)
5.1.1 Programming in a Single Doer	123	(3)
5.1.2 Programming in Multiple Doers	126	(4)
5.2 Virtual World Programming	130	(10)
5.2.1 Creating Virtual World as a Knowledge Network	130	(2)
5.2.2 Inhabiting the Virtual World with Mobile Entities	132	(2)
5.2.3 Providing Openness of the Virtual World	134	(1)
5.2.4 Observation of the Virtual World	135	(2)
5.2.5 Distributed Inference in the Virtual World	137	(2)
5.2.6 Mobility of the Virtual World in the Execution World	139	(1)
5.3 Mobility of Doers in Physical World	140	(4)
5.3.1 Movement of a Single Doer	140	(1)
5.3.2 Free Movement of Multiple Doers	141	(1)
5.3.3 Synchronized Movement of Multiple Doers	141	(1)
5.3.4 Movement of Multiple Doers by Turns	142	(1)
5.3.5 Adding Payloads to Mobile Doers	143	(1)
5.4 Moving and Acting in Physical World Directly	144	(7)
5.4.1 Sequential Movement in Physical World	145	(2)
5.4.2 Parallel Movement in Physical World	147	(1)
5.4.3 Combined Sequential-Parallel Movement	147	(3)
5.4.4 Adding Payload: Planting Trees	150	(1)
5.5 Programming in Integration of Physical and Virtual Worlds	151	(5)
5.5.1 Planting Trees in the United World	151	(2)
5.5.2 Observation in the United World	153	(1)
5.5.3 Programming of Spatial Dynamics	154	(2)
5.6 Conclusions	156	(1)
6 EXEMPLARY MISSION SCENARIOS	157	(28)
6.1 Coordinated Movement of a Group	158	(9)
6.1.1 Stepwise Movement of a Two-Level Hierarchy	158	(1)
6.1.2 Creation of a Persistent Infrastructure and Moving with It	159	(1)
6.1.3 Extending to Any Number of Layers	160	(1)
6.1.4 Simultaneous Movement of All Nodes in a Group	161	(1)
6.1.5 Moving to the Averaged Positions of Subordinates	162	(1)
6.1.6 Further Possible Group Movement Modifications	163	(1)
6.1.7 Reverse or Heads-First Movement	163	(1)
6.1.8 Movement in a Column	164	(2)
6.1.9 Integrating Different Movement Solutions	166	(1)
6.2 Physical Matter Delivery and Remote Processing	167	(4)
6.2.1 Most General Task Solution	167	(1)
6.2.2 Splitting into Subtasks	167	(1)
6.2.3 Adding Synchronization	168	(1)
6.2.4 Setting Specific Routes	169	(1)
6.2.5 Assigning Robots to Scenarios in Column Movement	169	(2)
6.3 Physical World Search Assisted by Virtual World	171	(10)
6.3.1 Creating the Distributed Virtual World	172	(2)
6.3.2 Top-Level Space-Cleaning Scenarios	174	(1)
6.3.3 Single-Step Multiple-Branch Search	175	(3)
6.3.4 Full-Depth Search for Polygons	178	(1)
6.3.5 Run Time Space Modification	179	(2)
6.4 Map-Based Collection of Samples	181	(1)
6.5 Conclusions	182	(3)
7 DISTRIBUTED MANAGEMENT USING DYNAMIC INFRASTRUCTURES	185	(22)
7.1 Distributed Creation and Reconfiguration of an Infrastructure	186	(6)
7.1.1 Hierarchical Infrastructure	186	(1)
7.1.2 Other Topologies: Centralized, Chain, and Ring	187	(3)
7.1.3 Infrastructure Modification	190	(2)
7.2 Dynamic Hierarchy Based on Physical Neighborhood	192	(3)
7.2.1 Finding the Most Central Unit	192	(1)
7.2.2 Creating Infrastructure from the Center	193	(2)
7.3 Basic Command-and-Control Scenario in WAVE-WP	195	(3)
7.3.1 Recursive Hierarchical Command and Control (CC)	195	(1)
7.3.2 Implementing CC in WAVE-WP	196	(1)
7.3.3 Adding Payload to the CC Implementation	197	(1)
7.4 Solving Distributed Management Problems	198	(3)
7.4.1 Hierarchical Resource Management	198	(1)
7.4.2 More Complex Management Scenarios	199	(2)
7.5 Air Traffic Management in Dynamic Environments	201	(5)
7.5.1 Creation of the Radar Neighborhood Infrastructure	201	(1)
7.5.2 Mobile Tracking of an Aerial Object	202	(1)
7.5.3 Simultaneous Multiple Tracking	203	(1)
7.5.4 Setting Up Global Control	204	(1)
7.5.5 Other Traffic Management Tasks	205	(1)
7.6 Conclusions	206	(1)
8 MORE CRISIS MANAGEMENT SCENARIOS AND SYSTEMS	207	(26)
8.1 Region Patrol by Mobile Robots	208	(5)
8.1.1 Patrolling by a Single Robot	208	(1)
8.1.2 Simultaneous Region Patrol by Two Robots	209	(1)
8.1.3 Possible Cooperation Between the Two Robots	210	(1)
8.1.4 Dynamic Patrol by Any Number of Robots	211	(2)
8.2 Distributed Dynamic Cognitive Systems	213	(2)
8.2.1 Semantic Representation of Distributed Cognition	213	(1)
8.2.2 Multirobot Patrol as a Distributed Cognitive System	214	(1)
8.3 Multirobot Hospital Scenarios	215	(5)
8.3.1 A Robotized Hospital	215	(1)
8.3.2 Hospital World Representation	216	(1)
8.3.3 State-Checking Scenario	217	(1)
8.3.4 Cleaning Scenario	218	(1)
8.3.5 Life Support Scenario	219	(1)
8.3.6 Multirobot Service Snapshot	219	(1)
8.4 Future Combat Systems	220	(3)
8.4.1 Advantages of Using WAVE-WP	220	(1)
8.4.2 Target Fusion and Distribution by the Infrastructure	221	(1)
8.4.3 Fusion-Distribution Scenario in WAVE-WP	222	(1)
8.5 Crises Management in Open Networks	223	(6)
8.5.1 Embedding Distributed WAVE-WP System	223	(1)
8.5.2 Establishing Higher Management Layer	224	(1)
8.5.3 Collecting All Infected Nodes	225	(1)
8.5.4 Finding Congested Links and Nodes	226	(1)
8.5.5 Inferring Possible Virus Sources	227	(1)
8.5.6 More Intelligent Solutions Required	228	(1)
8.6 Using Global Infrastructures in WAVE-WP	229	(2)
8.6.1 Hypothetical Infrastructure Sketch	229	(1)
8.6.2 Air Defense Programming Example	229	(2)
8.7 Conclusions	231	(2)
9 CONCLUSIONS	233	(8)
9.1 Summary of the Main Features of WAVE-WP	233	(2)
9.1.1 Starting from the Whole	233	(1)
9.1.2 The WAVE-WP Automaton	234	(1)
9.1.3 High-Level WAVE-WP Language	234	(1)
9.1.4 Distributed WAVE-WP Interpreter	234	(1)
9.2 Some Main Application Areas	235	(3)
9.2.1 Directly Accessing Physical World	235	(1)
9.2.2 Distributed Knowledge Processing	235	(1)
9.2.3 Operating in Physical World Under the Guidance of Virtual World	235	(1)
9.2.4 Intelligent Network Management	236	(1)
9.2.5 Advanced Crisis Reaction Forces	236	(1)
9.2.6 Massive Cooperative Robotics	236	(1)
9.2.7 Distributed Road and Air Traffic Management	237	(1)
9.2.8 Autonomous Distributed Cognitive Systems	237	(1)
9.2.9 Distributed Interactive Simulation	237	(1)
9.2.10 Global Defense and Security	238	(1)
9.3 Final Remarks	238	(1)
9.3.1 After the Final Remarks	239	(1)
9.4 Future Plans	239	(2)
APPENDIX: WAVE-WP SUMMARY	241	(4)
A.1 Extended Language Syntax	241	(2)
A.2 Compact Syntax Description	243	(1)
A.3 Permitted Abbreviations	243	(2)
References	245	(4)
Index	249