CONTENTS Foreword ... ⅶ PART Ⅰ. PRIMER ON AUTONOMOUS MOBILITY Chapter 1.Intelligent Motion Control : An Introduction ... 3 1.1 Autonomous Robotics ... 3 1.2 An Attempt to Define Intelligence ... 5 1.3 An Attempt to Understand Intelligence Implicitly ... 9 1.4 It is Hard to program the Motion of a Redundant System ... 14 1.5 Paradigms in Science and Technology ... 17 1.6 Technical Requirements and Specifications of Intellingent Autonomous Machines ... 22 1.7 What to Expect from an Intelligent Machine ... 25 Chapter 2. Evolution of Autonomous Mobile Robots ... 30 2.1 Introduction ... 30 2.2 Evolution of AMR ... 32 2.2.1 Wheeled AMR ... 33 2.2.2 Legged AMR ... 51 2.2.3 Underwater AMR ... 59 2.2.4 Airborne AMR ... 61 2.2.5 Recent developments ... 61 2.3.Structures of Intelligence ... 64 2.3.1 Problems and expertise in AMR area ... 64 2.3.2 Knowledge-based planning／control systems for AMR ... 68 References ... 72 Chapter 3. Elementary Concepts of Autonomous Mobility : Problems and Technical Requirements ... 76 3.1 Problem of Intelligent Mobility ... 76 3.2 Concept of Autonomous Intelligence ... 78 3.3 Structure and Problems of Integration ... 83 References ... 91 Chapter 4. Basic Theory of Cognitive Control ... 92 4.1 Structural Model of AMR Cognitive Controller ... 92 4.2 World Representation ... 98 4.3 Imaginary Worlds ... 98 4.4 Production System for Motion Planning ... 108 References ... 113 Chapter 5. Structure of Cognitive Controller for an Autonomous Mobile Robot ... 115 5.1 General Description ... 115 5.2 Operation of the Subsystems ... 119 5.2.1 Motion control ... 119 5.2.2 Sensor system(perception) ... 123 5.2.3 Knowledge system ... 125 References ... 132 PART Ⅱ. NESTED HIERARCHICAL CONTROL Chapter 6. Nested Hierarchical Controller for Cognitive AMR ... 135 6.1 Introduction ... 135 6.1.1 Focus of concentration ... 135 6.1.2 Control solutions to be considered ... 135 6.1.3 Knowledge organization for control purposes ... 136 6.1.4 Tree hierarchies vs stem hierarchies ... 140 6.2 Autonomous Control Systems(ACS) ... 141 6.2.1 Descriptionof ACS : demand and application ... 141 6.2.2 Strcture of ACS ... 142 6.2.3 A typical problem to be resolved by ACS ... 142 6.2.4 An approach to dealing with this type of problems ... 144 6.2.5 Decision-making processes of planning : control procedures ... 144 6.2.6 Nested hierarchical information refinement ... 147 6.2.7 Substitutionof positioning by tracking ... 147 6.2.8 Attempts to formulate a control problem for ACS ... 149 6.2.9 Nested hierarchical production system ... 154 6.3 Principles of Information Structure for Autonomous Control Systems(ACS) ... 156 6.3.1 Postulate of multiple representation ... 156 6.3.2 partitioning of representations ... 157 6.3.3 Representation of time ... 159 6.3.4 Knowledge bases : Semantic networks with context oriented interpretation ... 159 6.3.5 Tesselated knowledge bases ... 161 6.3.6 Resolution of knowledge ... 161 6.3.7 Generalization : belonging to a meaningful class ... 162 6.3.8 Look-up tables : a link betweenthe accepted paradigm and the automata theory ... 164 6.3.9 Special role of attention ... 164 6.3.10 Generalization oriented tesselation ... 165 6.3.11 Complexity of tesselation : e-entropy ... 165 6.3.12 Graph of the semantic network ... 166 6.3.13 Mechnism of recursive generalization ... 167 6.3.14 Practice of class recognition ... 167 6.3.15 Hierarchical vs heterarchical bonds ... 168 6.3.16 Pairs of adjacent levels ... 169 6.3.17 Built-in combinatorial operators : team of decision-makers ... 169 6.3.18 Using search for generating alternatives ... 170 6.3.19 Accuracy of representation ... 171 6.3.20 Evaluation of the size of a tile ... 172 6.3.21 Resolution of representation ... 173 6.3.22 Accuracy vs resolution ... 174 6.3.23 Nondeterministic nested referencing ... 175 6.4 Nesting and Its Efficiency ... 177 6.4.1 The phenomenon of nesting ... 177 6.4.2 An example of nesting ... 178 6.4.3 Efficiency of nesting ... 181 6.4.4 Storing the nested representation ... 183 6.4.5 Decision-making processes in a nested hierarchical structure ... 183 6.5 Hierachical Nested Decision-Making ... 185 6.5.1 General properties of the structure ... 185 6.5.2 Nesting of optimum decisions ... 186 6.5.3 Commutative diagram for a nested hierarchical controller ... 186 6.5.4 Decomposition of automata ... 187 6.6 Multiresolutional(Nested Hierarchical) Dynamic Programming in ACS ... 187 6.6.1 Optimum control of ACS ... 187 6.6.2 Generalization of the ACS decision-making processes ... 189 6.6.3 Extension of the Bellmans optimality principle ... 190 6.6.4 Strategies contemplated for ACS ... 191 6.6.5 Nested dynamic programming ... 192 6.7 Nested Hierarchical ACS ... 195 6.7.1 Subsystems ... 195 6.7.2 Intelligent module ... 197 6.7.3 Perception stratified by resolution ... 198 6.7.4 Maps of the world stratifide by resolution ... 199 6.7.5 Control stratijied by resolution into planning-navigating-piloting ... 200 6.7.6 Thesaural knowledge base ... 201 6.8 Discussion ... 202 6.8.1 Planning ... 202 6.8.2 Attention driven planning ... 202 6.8.3 Joint Planning : control process ... 203 6.8.4 Prediction ... 204 6.8.5 Contingencies ... 204 6.8.6 Compute architectures ... 205 6.8.7 Historical remarks ... 205 References ... 206 PART Ⅲ. INTELLIGENT MODULE Chapter 7. Planner ... 213 7.1 World Description at the Planners Resolution Level ... 213 7.1.1 Characteristics of the PLANNERs map ... 214 7.1.2 Patches and boundaries ... 216 7.1.3 Singular objects ... 217 7.1.4 Dealing with uncertainties ... 217 7.2 Algorithms of Geometrical Planning ... 218 References ... 235 Chapter 8. Navigator ... 236 8.1 Geometrical Navigation(G-Navigation) ... 237 8.1.1 Geometrical problems that arise at the Navigator level ... 237 8.1.2 Geometrical Navigator(G-Navigation) ... 239 8.1.3 Wandering Standpoint Algorithm(WSA) ... 243 8.1.4 General algorithm of Geometrical Navigation ... 248 8.1.5 Successor generation using sectors ... 250 8.1.6 Graph search ... 251 8.1.7 Implementation of Geometrical Navigator ... 252 8.2 Dynamic Navigation(D-Navigation) ... 253 8.2.1 Problem of Dynamic Navigation ... 253 8.2.2 "Slalom" situations ... 260 8.2.3 Topological passageways ... 265 8.2.4 Mathematical model of the moving robots ... 271 8.2.5 Dynamic programming in a sequential machine ... 275 8.2.6 Suboptimal algorithms of G／D Navigation ... 277 8.2.7 Implementation of Geometrical／Dynamical Navigation ... 281 8.3 Navigation in 2½-D Space ... 290 8.3.1 Representation for 2½-D world ... 291 8.3.2 Isolines ... 291 8.3.3 Representation of obstacles ... 296 8.3.4 Polygonization of isolines ... 297 8.3.5 Algorithm of navigation for 2½-D wold ... 302 8.3.6 Experimental results and discussion ... 307 8.4 Linguistic Navigation(L-Navigation) ... 309 8.4.1 Contingency analysis ... 309 8.4.2 Scheme of the Linguistic Navigator(LN) ... 313 8.4.3 WSA(G) for pictorial part of LN ... 321 References ... 323 Chapter 9. Pilot ... 326 9.1 Concept of Knowledge-Based PILOT ... 326 9.1.1 General description ... 327 9.1.2 Operation of IMAS ... 328 9.2 Knowledge-based structure of PILOT ... 330 9.3 Database : Representation and Modeling of PILOTs world ... 333 9.3.1 PILOTs perception ... 333 9.3.2 Terrain-image plane mapping ... 334 9.3.3 Classification of Pilots Information ... 340 9.3.4 Determining the vocabulary size ... 342 9.3.5 Quantitative Evaluation ... 343 9.4 Dealing with Imprecise Observations ... 346 9.5 Rule Base : Control Prescriptions ... 347 9.5.1 Rule causality relationship ... 347 9.5.2 Analytic model verbalization ... 348 9.6 Rule Evaluation ... 350 9.6.1 Fuzzy decision-making ... 350 9.6.2 Selection of minimum-time action ... 354 9.6.3 The operation of reporter ... 357 9.7 Pilots Language ... 359 9.8 Discussion of Results ... 364 References ... 369 Chapter 10. Cartographer ... 370 10.1 Functions ... 371 10.2 Information to Deal With ... 379 10.3 The Representation Model of Descriptive Information in Cartographer ... 381 10.3.1 General framework ... 381 10.3.2 Characteristics of the descriptive knowledge base ... 386 10.3.3 Example : creating a world description ... 387 10.3.4 Implementation ... 393 10.4 Map Decomposition for Planner ... 395 10.4.1 Structure of the system ... 395 10.4.2 Definitions ... 396 10.4.3 Graph formation ... 397 10.4.4 Mutual cutting of intrusion／protrusion pairs ... 400 10.4.5 Convex-convex case ... 408 10.5 Map Updating ... 409 10.5.1 Sensor overview ... 411 10.5.2 General approach to updating ... 412 10.5.3 Relationships between SMAP and INM ... 417 10.5.4 General algorithm of updating ... 420 10.5.5 Example of updating ... 422 References ... 422 Chapter 11. Actuation Control System ... 424 11.1 First Approach to Optimum Controller ... 424 11.2 An Example of an ACS for Indoor IMAS ... 425 11.3 Optimum Motion of IMAS ... 429 11.3.1 Problem of optimum control of actuation ... 429 11.3.2 Conditions of optimization ... 431 11.3.3 Simplifying assumptions ... 432 11.3.4 Mathematical statement of a problem of optimum control ... 432 11.3.5 Notes on final accuracy ... 433 11.3.6 Example 1.System with energy losses ... 433 11.3.7 Example 2.System with energy losses and final accuracy ... 434 11.4 Motion Control in a Stochastic Interval ... 436 11.4.1 Mathematical model development ... 436 11.4.2 Minimum estimated time motion control ... 438 11.4.3 Actuation controller ... 444 11.5 Calculation of the Switching Times ... 448 11.6 Design, Construction, and Implementation of IMAS Actuation Controller System ... 451 11.6.1 General description of ACS for IMAS ... 451 11.6.2 Design criteria ... 451 11.6.3 IMAS ACS hardware ... 452 11.6.4 IMAS ACS software ... 455 References ... 458 Chapter 12. Simulation and Testing ... 460 12.1 Structure of the Simulation System ... 460 12.1.1 World representation ... 461 12.1.2 Functional description of modules ... 463 12.2 Results of the Simulation ... 465 12.3 Testing : Objectives ... 495 12.3.1 General description ... 495 12.3.2 Testing the operation of geometrical navigator ... 502 12.3.3 Testing the Pilot operation ... 503 12.4 Program of Testing Activities ... 505 12.4.1 Seneors ... 505 12.4.2 Main computer ... 507 12.4.3 Actuation controller ... 508 12.4.4 Interface circuits ... 508 12.4.5 Communication ... 508 12.5 Description of the Activities ... 509 12.5.1 Actuation controller ... 509 12.5.2 Measurements and analysis of dynamic characteristic development of dynamic response models ... 510 12.5.3 Development of the Pilot ... 511 12.5.4 Vision system ... 511 12.5.5 Computing system development ... 511 12.5.6 Integrated location and navigation system ... 512 12.5.7 Software modifications and adjustments ... 512 12.5.8 Development of dynamic navigator ... 512 12.5.9 Development of descriptive, 2-½D geometrical cartographer ... 513 12.5.10 Integrated field tests ... 513 Afterword : Further Research and Development ... 514 Glossary ... 521 Index ... 543