030-Development and Implementation of a Self-Building Global

1 .Development and Implementation of a Self-Building Global Map for Autonomous Navigation Philip Redleaf Kedrowski Thesis submitted to the Faculty of the Virginia Polytechnic Institute and State University in partial fulfillment of the requirements for the degree of Master of Science in Mechanical Engineering Dr. Charles F. Reinholtz, Chairman Dr. Harry H. Robertshaw Dr. Don J. Leo April 24, 2001 Blacksburg, Virginia Keywords: Mobile Robots, Autonomous Vehicles, Robotics, Artificial Intelligence, Mapping, Calibration, Optimization, Simulation Copyright 2001, Philip R. Kedrowski 

2 .To Jeannine “grams” 

3 . Development and Implementation of a Self-Building Global Map for Autonomous Navigation Philip R. Kedrowski Committee Chairman: Dr. Charles F. Reinholtz Mechanical Engineering Department (ABSTRACT) Students at Virginia Tech have been developing autonomous vehicles for the past five years. The purpose of these vehicles has been primarily for entry in the annual international Intelligent Ground Vehicle Competition (IGVC), however further applications for autonomous vehicles range from UneXploded Ordinance (UXO) detection and removal to planetary exploration. Recently, Virginia Tech developed a successful autonomous vehicle named Navigator. Navigator was developed primarily for entry in the IGVC, but also intended for use as a research platform. For navigation, Navigator uses a local obstacle avoidance method known as the Vector Field Histogram (VFH). However, in order to form a complete navigation scheme, the local obstacle avoidance algorithm must be coupled with a global map. This work presents a simple algorithm for developing a quasi-free space global map. The algorithm is based on the premise that the robot will be given multiple attempts at a particular goal. During early attempts, Navigator explores using solely local obstacle avoidance. While exploring, Navigator records where it has been and uses this information on subsequent attempts. Further, this thesis outlines the look-ahead method by which the global map is implemented. Finally, both simulated and experimental results are presented. The aforementioned global map building algorithm uses a common method of localization known as odometry. Odometry, also referred to as dead reckoning, is subject iii 

4 .to inaccuracy caused by systematic and non-systematic errors. In many cases, the most dominant source of inaccuracy is systematic errors. Systematic errors are inherent to the vehicle; therefore, the dead reckoning inaccuracy grows unbounded. Fortunately, it is possible to largely eliminate systematic errors by calibrating the parameters such that the differences between the nominal dimensions and the actual dimensions are minimized. This work presents a method for calibration of mobile robot parameters using optimization. A cost function is developed based on the well-known UMBmark (University of Michigan Benchmark) test pattern. This method is presented as a simple time efficient calibration tool for use during startup procedures of a differentially driven mobile robot. Results show that this tool consistently gives greater than 50% improvement in overall dead reckoning accuracy on an outdoor mobile robot. iv 

5 . Acknowledgments I would like to acknowledge and thank God, the only creator of truly autonomous agents. As committee chairman, Professor Charles Reinholtz always treated me with respect and encouraged me to think creatively. Despite his many impressive professional achievements, he makes everyone feel as though they are his equals. He is the master at balancing between giving guidance and allowing his students to learn on their own. As a friend, Charlie is always willing to extend a helping hand whether it be a ride home or the use of his tools for a personal project. While this thesis work was in progress, Dr. Reinholtz demonstrated his selfless nature in a particularly extraordinary way. His cousin needed a kidney transplant and he volunteered to be the donor. In this particular operation, the organ receiver is out of the hospital the next day while the donor is typically bedridden for two to three weeks. He never wavered in his decision. Dr. Reinholtz has impeccable character in both his professional and personal life. Thank you Dr. Reinholtz, you are a true mentor. Thanks, to my committee members Dr. Harry Robertshaw and Dr. Don Leo. Dr. Robertshaw, I never had the pleasure of taking one of your classes, however I did learn a lot working as your graduate teaching assistant in ME 4006. I’ve always enjoyed our kayaking discussions and you’ll get the free kayak bilge pump if they are ever actual made. Dr. Leo, Advanced Controls I and II are among the most stimulating and challenging courses that I have taken. You are an organized and talented educator. Next, I want to thank my parents. They not only gave me life, but they never let me develop any misconceptions about how to live it. They are two of the most intelligent, creative, and talented people that I know; yet, they were always honest enough to let me see their faults. The only two stipulations they have ever put on me are that I do what makes me happy and that I always do my best. I’m trying guys, so far it’s been a good formula for life. I love you both more than you will ever know. To David Conner, while working on this project I have come to really understand and appreciate your skill as a designer and programmer. Countless details of the project were performed to perfection. In short, continuing a project that you started was a v 

6 .pleasure. I have learned a great deal from you and I know you will be an excellent professor. Thanks. Finally, I thank all of the students, both graduate and undergraduate, who have helped to enhance my academic experience here at Virginia Tech. In particular, I would like to thank the students involved with the Navigator project, both years. Mr. Bojangles, I’m finished buddy lets go play fetch! vi 

7 .Table of Contents List of Figures 1 Introduction 1.1 Definition of local and global maps....................................................................2 1.2 Thesis motivation................................................................................................3 1.3 Previous work .....................................................................................................6 1.4 Objective .............................................................................................................8 1.5 Thesis outline ......................................................................................................9 2 Literature review 2.1 Artificial Intelligence ..........................................................................................11 • Definition ..............................................................................................11 • Artificial vs. natural intelligence ...........................................................14 2.2 AI sub-fields and their relevance to navigation..................................................18 • Problem solving.....................................................................................18 • Pattern perception..................................................................................20 • Parallel processing and multi-agent systems .........................................23 • Fuzzy logic ............................................................................................25 2.3 Navigation control architectures.........................................................................28 • Behavioral-based control architectures .................................................28 • GOFAI control architectures.................................................................30 • Hybrid control architectures..................................................................32 2.4 World representation..........................................................................................33 • Dead Reckoning....................................................................................34 • Free space maps ....................................................................................35 • Object-oriented maps ............................................................................36 • Composite maps....................................................................................37 vii 

8 .3 Platform vehicle 3.1 Navigator hardware design ...............................................................................40 • Mechanical..........................................................................................40 • Electrical .............................................................................................42 • Modifications......................................................................................44 3.2 Navigator kinematics ........................................................................................48 4 Global map development, implementation, and simulation 4.1 Vector Field Histogram.....................................................................................52 4.2 Global map developing .....................................................................................54 4.3 Global map look-ahead .....................................................................................56 4.4 Navigation simulations .....................................................................................61 5 Optimized calibration of vehicle parameters 5.1 UMBmark test...................................................................................................69 5.2 Optimization technique and procedure .............................................................73 • Hooke and Jeeves optimization ..........................................................74 • Objective function ..............................................................................77 • Calibration procedure .........................................................................80 5.3 Calibration results .............................................................................................82 6 Implementation results 6.1 Practice course results..........................................................................................89 6.2 Conclusions and recommendations ....................................................................96 References .............................................................................................................................100 Appendix A. C++ code for look-ahead algorithm............................................................105 Appendix B. Matlab code for optimized vehicle parametric calibration.......................118 Appendix C. UMBmark Test Data....................................................................................136 Vita ........................................................................................................................................140 viii 

9 .List of Figures 1.1 Global and expanded local map of the vehicle’s environment ..................................3 1.2 Course used in the 2000 IGVC competition (Orlando, FL).......................................4 1.3 Problematic situation for local obstacle avoidance....................................................5 1.4 Some team members posing with Navigator and Artemis at the 2000 IGVC ...........7 2.1 Intelligent vehicle behaviors through connectionism ................................................12 2.2 Simplified block diagram of main computing components used in modern PC .......15 2.3 Typical string of neurons ...........................................................................................16 2.4 State space of two coin problem ................................................................................18 2.5 Map and search tree for traveling salesman...............................................................19 2.6 Three studies showing the increased computing speed in relation to increasing the number of processors used.........................................................................................24 2.7 Example fuzzy set for determining temperature in a shower faucet ..........................26 2.8 Block diagram of a typical fuzzy control system .......................................................27 2.9 Simple subsumption control architecture for a robot traversing a maze....................29 2.10 Linear decomposition of functional modules in a mobile robot control system........31 2.11 Intelligent subsumption control architecture for an autonomous vehicle ..................32 2.12 Cog, the humanoid robot developed at MIT ..............................................................33 2.13 Conventional GVG, reduced GVG, and internal free space representation of reduced GVG .............................................................................................................36 3.1 Navigator, the platform vehicle .................................................................................40 3.2 Main Navigator components prior to assembly .........................................................41 3.3 Sensing and computing hardware architecture in place on Navigator .......................42 3.4 Navigator functional block diagram ..........................................................................43 3.5 Free body diagram and equations for relating motor torque to drive force ...............45 3.6 Navigator just before installing new aluminum frame...............................................46 ix 

10 .3.7 Motor mounting plates and new motor mounting bracket.........................................46 3.8 New caster wheel and old caster wheel respectively .................................................47 3.9 Completed redesign of Navigator ..............................................................................47 3.10 Elevation side view of wheel .....................................................................................48 3.11 Plan view of Navigator ..............................................................................................49 3.12 Rotational motion of differentially driven vehicle about the instantaneous center ...49 4.1 Vector representation of obstacles in front of mobile robot ......................................53 4.2 Example Vector Field Histogram ..............................................................................54 4.3 Global map building in Cartesian coordinates, using dead reckoning.......................55 4.4 Illustration of the global look-ahead algorithm..........................................................57 4.5 Flow chart for the global look-ahead algorithm.........................................................58 4.6 Situation in which the VFH will override the global look-ahead algorithm..............60 4.7 Theoretical vehicle trajectory with global map building over multiple attempts ......61 4.8 Navigation Manager, the user interface to the controls on Navigator .......................62 4.9 Simulation test course with one trap..........................................................................64 4.10 Simulation on course that is more similar to the IGVC course .................................64 4.11 Vehicle using global map to avoid traps....................................................................65 4.12 Vehicle path and dead reckoned path with error due to 0.5% decrease in right wheel diameter ...........................................................................................................66 4.13 Second run using imperfect global map that was developed on the first run ............67 4.14 Vehicle path and dead reckoned path with error due to 3% decrease in the left wheelbase...................................................................................................................68 5.1 Dominant systematic dead reckoning errors cancel each other out when test is run in only one direction ..................................................................................................70 5.2 Aerial view of grid used for UMBmark dead reckoning test.....................................71 5.3 Six-yard square UMBmark test with no calibration ..................................................72 5.4 Flow chart for the Hooke and Jeeve’s optimization method .....................................76 5.5 UMBmark test results from a three-yard square and a six-yard square .....................78 5.6 Objective function vehicle simulations both clockwise and counterclockwise.........80 x 

11 .5.7 Non-calibrated and calibrated UMBmark test ...........................................................82 5.8 Non-calibrated and calibrated UMBmark test ...........................................................83 5.9 Non-calibrated and calibrated UMBmark test ...........................................................84 5.10 Non-calibrated and calibrated UMBmark test ...........................................................84 5.11 Three-yard test with no calibration ............................................................................86 5.12 Three-yard test, calibrated at three-yards ...................................................................86 5.13 Three-yard test, calibrated at six-yard........................................................................86 5.14 Six-yard test with no calibration ................................................................................87 5.15 Six-yard test, calibrated at three-yards.......................................................................87 5.16 Six-yard test, calibrated at six-yard............................................................................87 6.1 Outdoor test course for Navigator..............................................................................90 6.2 Counterclockwise test with a 2.5 meter look-ahead ..................................................91 6.3 Counterclockwise test with a 3.5 meter look-ahead ..................................................91 6.3 Clockwise test with a 3.5 meter look-ahead ..............................................................92 6.4 Demonstration that the look-ahead angle is useful even though the dead reckoned position differs from the actual position, due to dead reckoning errors.....................93 6.5 Photo sequence of Navigator on first attempt at the course with a trap.....................94 6.6 Clockwise test with a 3.5 meter look-ahead on course with a trap............................95 6.7 Three more runs in the clockwise direction with a 3.5 meter look-ahead on course with a trap ..................................................................................................................95 6.8 Example composite map array using evidence grid technique ..................................98 xi 

12 .Chapter 1 Introduction Over the past century, particularly the later decades, much work has been done in the field of robotics. Much of the initial literature on this topic is science fiction and depicts robots as human-like, or anthropomorphic, having intelligence and form, and interacting with humans as peers. Unfortunately, the capabilities shown by these fictional robots are anything but realistic [Conner, 2000a]. In 1968, Isaac Asimovs’ book, “Robot I,” developed the three laws of robotics and introduced the world to the concept of ethics and robotics [Asimov, 2000]. The three laws are as follows: 1. A robot may not harm a human being or, through inaction, allow a human being to come to harm. 2. A robot must obey the orders given it by human beings, except where such orders would conflict with the First Law. 3. A robot must protect its own existence, as long as such protection does not conflict with the First or Second Law. Although Asimov is often credited for coining the term “Robot,” Karel Capek actually used the term in 1917 to mean “worker [Fernandez, 2000].” This leads to the question, “What does the term robot actually mean?” Many widely accepted definitions of the word “robot” are found in the literature. David Conner reviews several of these and the interested reader is referred to his work. Conner goes on to establish his own definition. Conners’ definition, generally accepted by the author of this thesis, of the word robot is: a machine that uses its intelligence to interact autonomously with its changing environment [Conner, 2000a]. This leads to the question of autonomy. What does it mean to be autonomous? Merriam Webster defines autonomy as: existing or capable of existing independently [Merriam-Webster, 2000]. In the case of a robot, this is generally taken to mean independent of humans. However, this  2001 Philip R. Kedrowski 1 

13 .poses a contradiction to Asimovs’ second law of robotics. Further, in extreme cases, this could lead to breaking Asimovs’ first law. An example of this is presented in the popular new science fiction movie The Matrix. In this film, the robots, originally developed by humans, evolve and begin farming humans in order to use them as their source of power. This is an example of the robots protecting their own existence at the expense of normal human existence. This is an extreme case of Asimovs’ third law leading to the violation of his first and second laws, and thus the third as well. As previously mentioned, the fictional representation of a robot is a long way from reality, and therefore so is the above example. However, this author believes that it is necessary to consider the future repercussions of work being done in the present. For this reason the author would like to extend Conner’s definition. Hereinafter the term robot will be taken to mean: A machine that uses its intelligence to interact autonomously with its changing environment, such that it obeys Asimovs’ three laws of robotics. That said, it should be noted that a robot can take on many different forms and a can be designed to interact in many different environments. This thesis addresses a robot in the form of a vehicle navigating in the environment of the Intelligent Ground Vehicle Competition (IGVC) obstacle course. In particular, an algorithm is developed that allows an autonomous vehicle to build a global map of the environment and use it, in conjunction with a local map, to navigate through the IGVC obstacle course. This course is described in detail in later sections. 1.1 Definitions of Local and Global Maps In order for a vehicle to operate autonomously, it must have an adequate representation of the environment in which it is operating. Hereinafter, this is referred to as the vehicles’ map. The word map is both a noun and a verb. One definition of the word map used as a noun is: a representation, usually on a flat surface, of the whole or a part of an area [Merriam-Webster, 2000]. Note the distinction between representation of either whole or part of an area. This work refers to a map of the part of an area near the autonomous vehicle as the vehicles’ local map. The map of the whole area in which the autonomous vehicle is operating is referred to as the vehicles’ global map. Typically, the  2001 Philip R. Kedrowski 2 

14 .local map has a reference frame that is vehicle coincident and the global map has an external reference frame. This concept is illustrated in Figure 1.1. Vehicle Sand Trap Obstacle Goal Figure 1.1 Global and expanded local map of the vehicle’s environment. The word map, used as a verb, is defined as: to make a survey of for, or as if for, the purpose of making a map [Merriam-Webster, 2000]. To better understand this definition, the definition of the word survey is reviewed. Survey is defined as follows: to determine and delineate the form, extent, and position of (as a tract of land) by taking linear and angular measurements and by applying the principles of geometry and trigonometry [Merriam-Webster, 2000]. So to map an area is to examine it, record data, and reduce that data into a form that is understandable. The question remains, “Understandable to who?” In this work, “who” is Navigator, the autonomous vehicle developed at Virginia Tech in the academic year 1999/2000. This thesis focuses on autonomously exploring, recording position data, and using that data to better understand the global environment on the next exploratory run.  2001 Philip R. Kedrowski 3 

15 .1.2 Thesis Motivation The primary motivation for this work is to represent Virginia Tech competitively at the 10th annual IGVC. This competition requires graduate and undergraduate students to design and construct intelligent vehicles such that they can navigate an obstacle course autonomously. White lines bound the course on a grass surface and the layout varies from year to year. The obstacles include traffic cones and barrels, simulated asphalt, a hill, and a sand trap. A picture of the 2000 IGVC obstacle course, shown in Figure 1.2, illustrates a sample of all of these obstacles. IGVC’s objective in this event is for the student projects to be multidisciplinary, theory-based, hands-on, team implemented, outcome assessed, and based on product realization [IGVC, 2000]. Motivation for autonomous vehicles in general includes but is not limited to planetary exploration, unexploded ordnance (UXO) detection and removal, convoys, surveillance, security patrol, radioactive waste handling, and motor vehicle safety. Figure 1.2 Course used in the 2000 IGVC competition (Orlando, FL). Motivation for this thesis stems from the need for a global map when navigating the course at competition. Many mobile robot systems combine a global path-planning module with a local avoidance module to perform  2001 Philip R. Kedrowski 4 

16 .navigation [Ulrich, 2000]. A global path-planning module gives look-ahead information that can help the vehicle avoid potential trap situations, Figure 1.3. In Figure 1.3, the local path avoidance module uses the only information within the radius of the dashed circle. Based solely on this information, paths A and B are equal candidates for traversal, however a global planning module would override choice A and allow the vehicle to choose the correct path B. At point p the vehicle would choose path C. Further, a global path-planning module will allow the vehicle to know whether it is going the correct direction on the IGVC obstacle course. A local obstacle avoidance module alone will keep the vehicle on the course and moving, but it has no way of deciphering whether or not it is going in the correct direction. Global planning modules use some sort of global map. Typically, this map is initialized using prior knowledge of the environment in which the mobile robot is interacting. The rules of the IGVC state that the autonomous vehicles are to have no prior knowledge of the course [IGVC, 2000]. This is due to the fact there exists no prior knowledge of the environment in many of the applications for autonomous vehicles (planetary exploration, etc.). In addition, if Figure 1.3 Problematic situation for the course is pre-programmed, is the vehicle local avoidance considered intelligent? [Ulrich, 2000]. . However, multiple attempts are encouraged at the competition and if the vehicle learns the course on its own, through trial and error, it is considered intelligent. This work develops and tests a control algorithm that allows the vehicle to acquire data about the course during each run and use that information during each subsequent run. As the vehicle “learns” the course, it will develop smoother runs that are more efficient and allow it to generally explore further  2001 Philip R. Kedrowski 5 

17 .with each attempt. The number of attempts before completely mapping a course is expected to vary depending on the course difficulty. 1.3 Previous Work Graduate and Undergraduate students have been developing autonomous vehicles at Virginia Tech for the past five years. Although autonomous vehicles have many applications, these students have primarily focused on developing vehicles for entry in the annual IGVC. A table, detailing these vehicle’s and their successes, is found in Conner’s thesis [Conner, 2000a]. However, Virginia Tech’s most recent entries are not included and so the vehicles of the 1999/2000 academic year are shown here. Table 1.1 Virginia Tech entries in the 2000 Intelligent Ground Vehicle Competition. Vehicle Name Chassis Computation Design Awards Dynamic Results th st Artemis 3-wheeled Pentium Laptop 5 Place 1 Place Obstacle st differentially Bisection Method 1 Place Debris st driven Laser Range 1 Place Follow the Finder Leader Camera st th Navigator 3-wheeled Duel Pentium III 1 Place 5 Place Obstacle rd differentially Industrial PLC 3 Place Debris nd driven VFH 2 Place Follow the Laser Range Leader Finder Dual Cameras As shown in Table 1.1, Artemis swept all three of the dynamic events. Artemis was originally developed in 1998 and entered the competition under the name Nevel. In 1999, Nevel was redesigned and renamed Artemis. Then in 2000 effort was put into the software and navigation algorithm. The key to its success is its simple and well-tested mechanical, electrical, and software design. This has been Virginia Tech’s most successful entry. Each year during its five-year tenure entering vehicles in the IGVC, Virginia Tech has won first place in the design competition. In 2000 the award went to Navigator. Navigator implements a modular design in the mechanical, assembly, computing  2001 Philip R. Kedrowski 6 

18 .hardware, and also in the navigation software. From a design perspective, this offers advantages in that it can be easily maintained and upgraded. Figure 1.4 shows some of the Autonomous Vehicle Team (AVT) members posing with Navigator and Artemis at the 2000 IGVC in Orlando, Fl. Note, the banner displays the original competition name “International Unmanned Ground Robotics Competition” instead of the new competition name “Intelligent Ground Vehicle Competition.” Figure 1.4 Some team members posing with Navigator (left) and Artemis (right) at the 2000 IGVC. Both Artemis and Navigator traverse the course using navigation modules that are based on local map information. Artemis uses a simplified Voronoi method in which it locates the brightest pixel on each side of the camera image and chooses a navigation point that is the bisector of these two pixels. This navigation scheme assumes that the white course boundary lines will be the brightest pixels. If an obstacle falls in the path of the navigation point, the Laser Range Finder (LRF) detects it and the obstacle is avoided using subsumption. Voronoi diagrams and subsumption control architectures will be explained in more depth in chapter two. Navigator uses a local obstacle avoidance  2001 Philip R. Kedrowski 7 

19 .module known as the Vector Field Histogram (VFH). Line position data is obtained, using duel cameras, and converted to polar coordinates. Further, obstacle position data is captured in polar coordinates directly using the (LRF). These data sets are fused and presented in a VFH, which is a convenient method of representing the obstacles and lines in front of the vehicle. Velocity and heading commands are then issued based on the VFH. This navigation module sends the vehicle in the direction of low obstacle density. The VHF local obstacle avoidance method is discussed at length in chapters three and four. Since both vehicles navigate based on local sensor data, they have no global representation of their environment. The main disadvantage of this is that these vehicles have no preference as to which way they are traversing the course. In other words, the navigation modules can be working perfectly while the vehicles are going the wrong direction. Another disadvantage is that the vehicles have to move slowly, first sensing a necessary turn then executing it. If the vehicles had a global map, they could look ahead and initiate turns early thus giving a smoother motion profile and higher velocity through out the turn. 1.4 Objective This thesis starts with the proven base mechanical platform vehicle, Navigator, and addresses higher-level artificial intelligence issues. Specifically, a global path- planning module is added to the existing local obstacle avoidance module known as the VFH. However, an extra level of complexity exists since the vehicle has no prior knowledge of the global environment. In other words, the global path-planning module cannot use an initialized global map. Hence, Navigator must first explore, and acquire data in order to map the environment. The quality of this map will increase with each successive exploratory run. As the global map quality increases, the global path planners’ navigation commands are given a higher weighting relative to the VFH navigation commands. In effect, during early exploratory runs navigation decisions are made almost solely by the VFH and as the map quality increases the navigation decisions shift to being based almost solely on the global path planning module. An analogy to this  2001 Philip R. Kedrowski 8 

20 .is a person who moves to a new town with a new job and a new house. At first, the person will inspect every turn, and probably make a few mistakes, on the path from his/her new home to his/her new job, but after going to and from work every day for a few weeks the person will surely know the route and put relatively little thought into each individual turn. 1.5 Thesis Outline This thesis presents the development and implementation of the aforementioned objective. Chapter two begins by defining artificial intelligence (AI) coupled with a brief discussion of AI verse natural intelligence. It then goes on to survey many AI areas and give their relevance to navigation. Chapter two then proceeds to discuss navigation control architectures including behavioral-based, sense-model-act, and hybrid systems. Chapter two finishes with a discussion of machine world representation methods, i.e. map techniques. Chapter three lays out the electrical and mechanical design of the platform vehicle, Navigator. This includes the changes made during 2000/2001 academic year. This chapter ends with the development of the vehicle kinematic equations. Chapter four describes the global map building technique and the architecture of the global path- planning module. This chapter gives some results of simulating this method under perfect conditions and then goes on to simulate the effects of systematic dead reckoning errors. Chapter five begins by quantifying Navigator’s dead reckoning error using a procedure known as the UMBmark test. Next, a calibration tool is developed for use in optimizing the vehicle parameters such that the systematic dead reckoning errors are minimized. Last, chapter five gives the results showing increased dead reckoning accuracy using this calibration tool. Finally, chapter six presents actual implementation results on a real course. A comparison is made between the theoretical and actual results, and then chapter six finishes with conclusions and future recommendations.  2001 Philip R. Kedrowski 9 

21 .Chapter 2 Literature Review Can computers think? “Exactly what the computer provides is the ability not to be rigid and unthinking but, rather, to behave conditionally. That is what it means to apply knowledge to action: It means to let the action taken reflect knowledge of the situation, to be sometimes this way, sometimes that, as appropriate [AAAI, 2000].” If intelligence is simply complex conditional behaviors, then it follows that the complexity of the behaviors computers exhibit should increase at the same rate as computing power and memory increases. Today a hand held computer has as much computing power as a computer that once filled an entire room. Yet, advances in artificial intelligence (AI) research have shown relatively little progress. In fact, Raj Reddy was forced to defend AI research in his 1988 American Association of Artificial Intelligence (AAAI) Presidential Address, because after twenty-five years of sustained support, Defense Advanced Research Projects Agency (DARPA) program managers were asking the tough questions [Reddy, 1988]: -What are the major accomplishments in the field? -How can we tell whether you are succeeding or failing? -What breakthroughs might be possible over the next decade? -How much money will it take? -What impact will it have? -How can you effect technology transfer of promising results to industry? Reddy makes a good case for AI in his address, but this example gives reveals that advances in AI have not been as evident nor as rapid as advances in computing resources. Computers simply do what humans instruct or program them to do. As technology improves, computers can perform more of these instructions at a faster rate.  2001 Philip R. Kedrowski 10 

22 .In effect the computers are doing their job well, so perhaps rather than asking the question, “Do computers think?” we should ask the question, “Are humans intelligent enough to understand intelligence?” In his book published in 1985, Jackson states that understanding intelligence remains an unsolved challenge to our intelligence [Jackson, 1985]. Today, despite much effort, the question of intelligence is still unanswered. Massachusetts Institute of Technology has an AI lab whose efforts are focused directly on this goal. Their aims are two-fold: to understand human intelligence at all levels, including reasoning, perception, language, development, learning, and social levels, and to build useful artifacts based on intelligence [MIT AI, 2000]. However, regardless of whether or not machines can ever be truly intelligent, AI research has shown that even limited forms of machine intelligence have great utility [Jackson, 1985]. In particular, AI research has had a positive impact in the area of autonomous vehicle navigation. 2.1 Artificial Intelligence Definition - Merriam-Webster gives two definitions of artificial intelligence [Merriam- Webster, 2000]: 1) The capability of a machine to imitate intelligent human behavior. 2) A branch of computer science dealing with the simulation of intelligent behavior in computers. This leaves room for individual interpretation and ambiguous answers for what exactly AI really is. This leads to much debate on what constitutes an intelligent machine. For instance, is a computer that is programmed to distinguish between a circle and a square intelligent? The answer is maybe. It depends on how it does it. If it could use the same algorithm it uses to detect the circle and square to detect a triangle, then yes, it is considered AI. However, if it is choosing based on matching a preprogrammed circle and square, and would be stumped by any other shape, then it is not considered AI. So one test of a true AI solution is to ask, “Is it scaleable to larger problems and is it adaptive to variations of the problem [Schank, 1991]?” This still does not concretely  2001 Philip R. Kedrowski 11 

23 .address the issue of what really constitutes AI. Shank gives four prevailing viewpoints of what AI means: 1) AI means magic bullets. 2) AI means inference engines. 3) AI means the “gee whiz” view. 4) AI means having a machine learn. The magic bullet view asserts that intelligence is difficult to put into a machine because it is knowledge dependant. Since the knowledge-acquisition process is complex, one way to address it is to let the machine be computationally efficient such that it can connect things without having to explicitly represent anything [Schank, 1991]. This is the basis for connectionism. Consider Figure 2.1 for a simple example of a machine that could be considered intelligent based on connectionism. This vehicle is equipped with two heat sensing devices that positively excite the actuators at a rate proportional to the amount of heat to which they are exposed. It is easily seen that the vehicle can be designed to be either attracted to or repelled from the heat source based on the connections between the sensors and the actuators. From the perspective of the casual observer, this machine is intelligent and seems to either “fear” the heat or exhibit “aggression” toward the heat. Obviously, the complexity of the behaviors is increased with an increase in connections between senses and actions. This method of AI has been used extensively in the field of robotics.  2001 Philip R. Kedrowski 12 

24 . Heat source Figure 2.1 Intelligent vehicle behaviors through connectionism a) fear b) aggression The inference engine is a key element in the success of expert systems. Expert systems are a development in which the AI scientists would study experts in a field then put this expert knowledge into the computer in a form that it could follow. Once initialized with a base of knowledge in a particular area, these expert systems can make some interesting and useful decisions [Schank, 1991]. Some examples of the broad uses for expert systems include [Reddy, 1988]: • Kodak has used an Injection Molding Advisor to diagnose faults and suggest repairs for plastic injection molding mechanisms. • American Express uses a Credit Authorization System to authorize and screen credit requests. • Federal Express uses an Inventory Control Expert to decide whether or not to store spares. Some critics would argue that although these expert systems are impressive and useful, they are not AI. They take the standpoint that the real AI in these systems lies in the ability of the AI scientist to find out what the experts know and to represent the information in some reasonable way. The counter argument to this is that the AI exists in  2001 Philip R. Kedrowski 13 

25 .the computers’ ability to infer the next set of knowledge from the previous set. In other words, the AI is in the inference engine of the expert system, not in developing the knowledge base of the expert system [Schank, 1991]. The gee whiz view maintains that for a particular task, if no machine ever did it before, it must be AI. An example of this is chess playing programs, these were considered AI years ago, but today most would say that they are not. They were AI as long as it was unclear how they worked, but once this became clear, it looked a lot more like software engineering than AI. This gee whiz phenomena stems from peoples eagerness to confuse getting a machine to do something intelligent with getting it to be a model of human intelligence. The fourth view that Shank discusses is the one he personally espouses. It is the view that AI entails learning. This is to say that the machines’ intelligence should get better over time. He maintains that no system that is static, that fails to change as a result of its experiences, looks smart. The problem with this, he states, is that according to the definition, no one has actually implemented AI [Shank, 1991]. Depending on your perspective, the assertion that no AI has actually been accomplished is either disheartening or exciting. It is disheartening if one believes that much work has proven fruitless, but it is exciting when considering the proverbial “brass ring” is still out there waiting to be grasped. However, less stringent viewpoints exist concerning the issue of AI. Raj Reddy gives a short list, provided by Alan Newell, of intelligent system characteristics. It states an intelligent system must [Reddy, 1988]: • operate in real time; • exploit vast amounts of knowledge; • tolerate error-full, unexpected and possibly unknown input; • use symbols and abstractions; • communicate using natural language; • learn from the environment; and • exhibit adaptive goal oriented behavior.  2001 Philip R. Kedrowski 14 

26 . The degree to which an intelligent machine exhibits the above characteristics still lends itself to much ambiguity and individual interpretation, depending on the machines application. Regardless of whether or not AI has been or ever will be truly accomplished, many useful advances have been achieved in its pursuit. This may be an area in which success lies in the journey and not the destination. Artificial Versus Natural Intelligence – A classic experiment to determine whether a machine exhibits intelligence is the Turing Test. This is a test in which there is a machine in one room and a human in another, they are given communication through a screen and keyboard to a person in a third room. If this third party is unable to distinguish between the human and the machine, then the machine is intelligent. This test has not yet been seriously attempted, since no machine has displayed enough intelligence to perform well [Jackson, 1985]. However, this underlying fascination with replicating human intelligence on a machine leads to some discussion comparing the two. When comparing human and machine intelligence, one must first inspect the hardware implemented in each. First let us inspect the modern Personal Computer (PC), Figure 2.2. The PC has two main modes of memory storage. Long term memory is stored on the hard drive and the short-term memory is in the Random Access Memory (RAM). Note, the PC also implements a third type of memory called Read Only Memory (ROM). ROM, located permanently on the motherboard, contains boot up information and initializes contact between the hard drive and the RAM. When working on a computer, all things seen and done immediately are stored in the RAM. In order to store information permanently, it must be transferred to the hard drive. If the computer looses power before the information is transferred to the hard drive, the information will be lost. Further, if the RAM is full, information must be stored temporarily on the hard drive in order to make room for new information. The processor serves as the “middle man” between the RAM and the hard drive. The higher the processor speed, the faster information can be processed and transferred between the hard drive and the RAM. Some specialized or industrial computers use two or more processors in parallel. As shown in chapter three, the Navigator vehicle implements two processors. Real time calculation speed is limited by the processor speed and amount of RAM. Permanent  2001 Philip R. Kedrowski 15 

27 .memory storage is limited by the size of the hard drive. The PC processes information in the form of 5-volt electrical pulses, a group of eight of these binary pulses is referred to as a byte. Today, for around $2,000 one can purchase a PC with a 1,000MHz processor, 128megabytes of RAM, and 40gigabytes of hard drive space [Gateway, 2000]. HARD PROCESSOR RAM DRIVE Figure 2.2 Simplified block diagram of main computing components used in a modern PC. For comparison, it has been discovered experimentally that a human has three types of memory. The first one that will be discussed is Sensory Information Storage (SIS). SIS occurs in tenths of a second, it is the after image one sees when rapidly closing his or her eyes. The second type of memory is Short Term Memory (STM). This is somewhat analogous to the RAM in a PC. STM lasts for about 30 seconds and the information stored there is rapidly replaced when a subject is presented with new information. Finally, Long Term Memory (LTM) can last up to the duration of a humans life. Observations have been made leading to the idea that STM traces are transient electric events that eventually consolidate into LTM through chemical and biological changes in the brain [Jackson, 1985].  2001 Philip R. Kedrowski 16 

28 . The nerve cell or neuron is the fundamental building block of the brain, Figure 2.3. The human brain contains approximately 12 billion neurons. Figure 2.3 shows how the neurons connect to one another. The dendrites serve as the input signal carriers and the axonal branches serve as the output signal carriers. Each neuron has between 5,600 and 60,000 dendritic-axonal connections. These connections are made through what is known as the synapse, by process of synapses. Electrical impulses transmitted at the synapses add or subtract from the magnitude of the voltage. When the magnitude reaches approximately 10 millivolts, an impulse is fired down the neuron’s axon. This is somewhat different from the binary “on-off” method by which Figure 2.3 Typical string of neurons [Jubak, 1992]. the computer transmits information. Note, the myelin sheath is a layer of fat surrounding the longer axons, Figure 2.3. It serves to increase conduction in the axon and insulate it from neighboring electrical activity [Jackson, 1985]. The power of the brain, it seems, lies not in vast amounts of memory storage, but in its’ ability to process information through trillions of parallel connections. Assuming an average number (27,200) of dendritic-axonal connections per neuron pair, there is approximately 160 trillion connections in the average human brain. Knowing that the brain operates at around 200 Hz (note, this is small compared to a 1,000MHz processor of a PC) and approximately 1% of the dendritic-axonal connections are active at any  2001 Philip R. Kedrowski 17 

29 .given time, the brain can perform on the order of 300 trillion operations per second [Reddy, 1988]. Although some analogies can be drawn between the functions of the computer and the brain, much still needs to be learned about the operations of the brain. One distinction to be noted is that the power of the brain is not its processor speed but its parallel processing abilities. Thus, fundamentally the computer and brain don’t operate similarly and therefore have differing strengths and weaknesses. For example, the average human brain can function faster than 1,000 supercomputers when processing vision and language, yet a 4 bit microprocessor can outperform the average brain in multiplication. This suggests that artificial intelligence, if ever achieved, will have different attributes than natural intelligence [Reddy, 1988]. The next debate that arises when comparing artificial and natural intelligence is concerning philosophical issues involving conscious thought, the conscience, and the soul. Is it possible for a machine to decipher right from wrong? Will intelligent machines try to better their own lives? Can they experience emotions such as love, hate, fear, anger, forgiveness, and compassion? This debate leads to discussions concerning the existence of god and the soul. This thesis will not delve too deeply into the subject. However, it should be noted that this author, in all of his research, has never seen any indication that machines will ever be capable of achieving conscious thought, a conscience, or a soul. They are, in fact, machines and we as the designers of these machines are not gods. Conners’ work presents an eloquently written section concerning philosophical foundations on this subject [Conner, 2000a]. 2.2 AI Sub-fields and Their Relevance to Navigation Many different approaches have been used in the pursuit of artificial intelligence. Although the general goal of all of these approaches is to unlock the secret of human intelligence, the differing techniques tend to be best suited for differing applications. This thesis is concerned with the problem of navigating an autonomous vehicle, so this section will focus on the areas of AI research that have proven useful, to varying degrees, for this application. These sub-fields include problem solving, pattern perception,  2001 Philip R. Kedrowski 18