Architectures for Controlling an Intelligent Autonomous Vehicle
Download 1.23 Mb.
|
- Navigate this page:
- Abstract
- Acknowledgements
- Table of Contents
- Table of Figures
- Chapter 1
- Chapter 2 Related Work
- Introduction
- Control
|
Architectures for Controlling an Intelligent Autonomous Vehicle By John Stevens Presented as a Partial Fulfillment of the Requirements for an MSc. in Intelligent Knowledge-Based Systems Department of Computer Science University of Essex Supervisor: Dr. Sam Steel Presented September, 1994 Abstract Surname: Stevens Other Names: John Kenneth Qualification Sought: MSc in Intelligent Knowledge Based Systems Title of Project: Architectures for Controlling an Intelligent Autonomous Vehicle Supervisor: Dr Sam Steel Artificial intelligence researchers have developed several styles of IA V architectures, mapping systems, and planners. Considerable debate surrounds the utility of each. This dissertation contributes to these debates. This document reports on the experimental testing of three architectures: a reaction-based architecture implemented on an economical mobile vehicle developed for this project; a subsumption architecture, and a combined architecture integrating subsumption with a non-linear planner, the latter two of which were implemented on a University of Essex Marvin vehicle. The results of this research suggest four conclusions. First, simple, inexpensive mobile vehicles can successfully perform basic behaviours, and the technology and software for such vehicles can be rapidly developed and tested. Second, ultrasound and infra-red sensors limit the ability of a mobile vehicle. Future use of alternative sensors, such as vision, may well yield improved performance. Third, while sUbsumption architecture does not live up to some of the claims made by its designers, it can facilitate successful goal completion by an IA V. Fourth, subsumption architectures can be effectively integrated with non-linear planners to improve vehicle performance. The final chapter summarises the findings of this work and explores the potential avenues for future research suggested by these findings. ii Acknowledgements My first thanks have to go to Kimberly Fisher who has spent many hours copy-editing and correcting English mistakes in my draft texts, assistance rendered necessary by my dyslexia. This special lady also has to be thanked for putting up with me during the production of this report. I would also like to express my gratitude to Paul Chernett, and Robin Dowling, who provided both technical support and comments to assist the implementation of my ideas on the robots. I extend similar gratitude to Stuart Soltysiak, who also offered advice over many cans of coke and games of pool. I would like to acknowledge Mr. Malcom Lear's input into the development of the clocking circuitry, PCB board art work, and the small mobile vehicle. Without his technical input this development would have been more difficult to complete. Finally, of course, I wish to thank my supervisor, who nudged me in constructive directions, while allowing me to do the hard work myself. iii
I declare that any use of, or reference to, the work of others has been explicitly acknowledged in this dissertation. John Stevens iv
Title Page Abstract Acknowledgements Acknowledgement of Exam Regulation 6.5(c) Table of Contents Table of Figures 1 ii iii iv v vii 1. Introduction 1 2. The Subject Area 2.1 IA V Architectures Process Control Systems Plan then Execute Architectures Subsumption Architectures Combined Architectures Non Symbolic Methods Self Organising Architectures Summary 2.2 Mapping Systems Geometric Mapping Systems and Dead Reckoning Landmark Mapping Topological Mapping Summary 2.3 Planning Systems Path Planners Non-Liner Planning Hierarcal Plans Planning to Plan 2.4 Attention 2.5 Summary 5 6 6 7 9 12 13 15 16 16 17 17 18 18 19 19 21 22 23 23 23 3. An Implementation of a Reactionary IA V Architecture 3.1. Vehicle Developed 3.2. Software Developed 3.3. Experimental Results 3.4. Future Work 3.5. Summary 24 26 28 29 30 30 v
4.1. Hardware 33 Sensor Details 34 Hardware Modification 35
Reflex Module 36 Obstacle Avoidance Module 37 Wall Following Module 37 Infra Red Location Module 38 Implementation Details 39 4.3. Experimental Results 39 Comments on the Performance of the Vehicle 41 Comments on the Performance of Subsumption 41
Mixing 'C' with PROLOG 47 Plan-then-Execute Behaviour 48 Topological Path Planner 48 Subsumption Interface with Topological Path Planner 50
k. top_planner.pl 1. Combination Test result Al A2 A3 A7 A8 AlO A19 A25 A29 A31 A38 A40 vi
1.1. Picture of Robots 3 2.1. Diagram of Process Control Architecture 7 2.2. Diagram of Process Control Architecture 7 2.3. Diagram of Plan-then-Execute Architecture 7 2.4. Diagram of Plan-then-Execute Architecture 7 2.5. Brooks' Modular AI Diagram 9 2.6. Brooks' Behaviour Based Control Architecture Diagram 9 2.7. A Subsumption Network 10 2.8. Alice Architecture 13 2.9. Fuzzy Logic Language 14 2.10. Topological Map 18 2.11. Free Space Representation Map 20 2.12. NaT Map 20 2.13. Non-Linear Plan 22 2.14. Hierarchical Plan 22 3.1. Picture of Small Robot 25 3.2. Circuit Diagram for Small Robot 27 3.3. Circuit Diagram for Op-amp 27 3.4. Pseudo Code for Reaction Software 28 3.5. Table of Results of Reaction Software Experiments 29 4.1. Picture of Department Robot 33 4.2. Diagram of Positioning of Ultrasound Sensors 35 4.3. Subsumption Network Diagram 36 4.4. Pseudo Code of Wall Following 38 4.5. Pseudo Code of Subsumption Control Network 39 4.6. Table of Results of Subsumption Experiments 40 5.1. Architecture Diagram of Combined Approach 46 5.2. Pseudo Code for Plan-then-Exicute Behaviour 48 5.3. Topological Map Reprsentations 49 5.4. Topological Map Used in Testing 50 5.5. Table of Results of Combined Architecture Experiments 51 5.6 Architecture Diagram of Possible Future Work 54 Vll
Introduction 1.0 Introduction For centuries, people have pondered the possibility of developing machines capable of independent thought. In the nineteenth century, writers like Robert Lewis Stevenson founded the literary genre which would develop into today's science fiction - a genre replete with robotic beings who have reached a level of sentiency and ability which exceeds human capacities. While the fans of science fiction literature and fihns may fantasise about interactions with the likes of Data or C3PO, the real life world of artificial intelligence research is now - and for some time in the future, will remain - far more mundane. The researchers who undertook the first attempts to write programs to allow autonomous mobile vehicles to act with a degree of intelligence soon made two discoveries. First, they learned that artificial intelligence programming must enable the mobile vehicle to perform basic levels of decision making, such as figuring out how to navigate differing terrains and learning to avoid obstacles. Second, they learned that humans must develop complex programs to enable machines to perform even such seemingly simple tasks. To make this programming challenge manageable, researchers have split the levels of decision-making into manageable and understandable modules. Many early experiments centred on the execution of a single behaviour, such as path planning. By adopting this simplified approach, computer scientists soon succeeded in expanding the capacity of Intelligent Autonomous Vehicles (IAVs). This success, however, generated a new and challenging problem - mobile vehicles cannot cope with independent movement without constant attention from researchers if they do not possess the ability to integrate the performance of several behaviours. Until very recently, only a few research groups demonstrated interest in the design of integrated architectures. The process of organising behaviours into functional, combined control systems has recently become one of the major themes of IA V research. This project, investigates such systems through the implementation of three different control strategies. Chapter Two offers a brief overview and analysis of the literature on IA V behaviour control. The major developments in IA V architecture research, discussed in this chapter in a slightly idealised chronological order, are: 1) early process control systems; 2) plan-then-execute architectures; 3) reaction-based systems; 4) subsumption architectures; 5) combined architectures; 6) non-symbolic methods; and 7) self organising architectures. This chapter additionally offers discussion of the techniques developed to facilitate mapping, planning, and attention in mobile vehicles. The three subsequent chapters discuss the implementation of three of these architectures and the mobile vehicles on which they were tested. Both of these vehicles are pictured in Figure 1.1. Chapter Three records the results of the implementation of a reaction-based architecture. As such architectures may have a simple design, this chapter details an effort to develop a minimal architecture to produce a single behaviour from a small mobile vehicle. The vehicle designed for this experiment (see Figure 1.1) uses a single layer reactive control system which enables it to move around its environment without damaging itself. The simplicity of this design permitted rapid development and testing of the architecture, and also demonstrated that utility of this hardware and software for low-budget projects. 2
Figure 1.1. Chapter Four reports on a re-evaluation of subsumption architecture. This architecture which was developed by Rodney Brooks and detailed in Brooks (1986) was implemented on one of the departmental Marvin vehicles, Ford, shown in Figure 1.1. Chapter Four begins with a description of the test vehicle, then proceeds to discussion of modifications made on Ford, including justification for these changes. The chapter then offers an evaluation of the architecture. Ford was able to perform behaviours such as ret1ex action: avoid obstacles: follow walls: and tind infra red beacons. Chapter Five records the implementation and testing of an architecture combining subsllmption and plan-then-execute techniques. Ford again served as the base vehicle for these experiments. The results reponed in Chapter Five indicate the compatibility of these two architectures. This combination pemlits a vehicle to make lise of the advantages of both systems: the suitability of reaction-based subsllmption for addressing immediate dewlopments in the environment: and the capacity of the
Chapter Six fIrst provides additional comment on the different architectures presently under investigation in the artificial intelligence community. The experimental results obtained are then summarised, and possible future applications of these findings are considered. The text closes with discussion of the directions in which research into Intelligent Autonomous Vehicle architectures could head in the future. 4 Chapter 2 Related Work Contents 2.0 Introduction 2.1 IA V Architectures Process Control Systems Plan-then-Execute Architectures Subsumption Architecture Combined Architectures Non Symbolic Methods Self-Organising Architectures Summary 2.2 Mapping systems Geometric Mapping and Dead Reckoning Landmark Mapping Topological Mapping Summary 2.3 Planning Systems Path Planners Non-Linear Planners Hierarchical Plans Planning to Plan 2.4 Attention 2.5 Summary 5
In this chapter, I detail the major developments in the published research on the control of autonomous mobile vehicles which I have reviewed to ground my own architectural experiments detailed later in this dissertation. The first and largest section contains discussion of the major IA V control architectures described in the literature, focusing on the connections between the individual modules of the control system. I then examine the research covering two of the more important modules. The second section of this chapter details developments in IA V mapping, and the third section offers an examination of the research on planning. The fourth section contains discussion of IA V attention. 2.1 IA V Architectures Initially, the researchers working with IA V s concentrated on functionality of individual behaviours, such as obstacle avoidance or path planning. Only a few devoted minimal effort to designing strategies for organising these behaviours into a combined control system. The following sub-sections of this report provide details of the major developments in IA V architecture research in chronological order, beginning with process control systems, then moving on to plan-then-execute architectures, subsumption architectures, combined architectures, non-symbolic methods, and self organising architectures. Members of the IA V community now generally regard architectural design as one of the most important areas of research on this field. 2.1.1 Process Control Systems Before the AI community developed an interest in IA V s, industrial technicians had designed process control architectures for robots. Examples of early process control architectures can be found in Grover (1987). Academic research consequently began with examination of these systems, which are generally implemented by a single layer of process control through which a given input stimulates an output. This structure may be diagrammed as follows: 6
--_\ / React (Execute) Figure 2.1 This architecture has been implemented by many people to control IA V s, an example of which can be found in Miller et. al. (1992), and is shown in Figure 2.2. Sense for obstacle --_\ / If obstacle in front, tum left Figure 2.2 The simplicity of these initial IA V architectures enables a mobile vehicle to function in a relatively static environment, such as a production line, where it would perform generally uncomplicated manoeuvres to achieve a single goal. AI researchers soon found that process control systems did not facilitate more complex behaviour in dynamic environments, and instigated a search for a more flexible IA V architecture. Download 1.23 Mb. Share with your friends:
|
