Architectures for Controlling an Intelligent Autonomous Vehicle
Download 1.23 Mb.
|
- Navigate this page:
- 2.1 . 4 Combined Architectures
- 2.1.5 Non Symbo l ic Methods
- .•...•...•.
- .lI.. . •. .lo..lJo.. .•. .lo. lJo. . )o"." ).. .•• ...a... .•. .
- ""Y}ry .,.. """)r
2.1.2 Plan-then-Execute Architectures This search gave rise to a second approach to IA V control, a functionally decomposed "sense, plan-then-execute" architecture. Much like the process control systems, plan-then-execute architectures also generally have only a single layer of abstraction, although there are exceptions. The reader will notice the similarities between Figure 2.3 and the preceding figures: Sense --_\ / Plan --_\ / Execute Figure 2.3 The similarities likewise appear with the adaptation for a mobile vehicle: Sense and Interpret the Environment --_\ / Plan Response(s) --_\ / Execute Figure 2.4 7 This architecture converts sensory information into a symbolic internal representation of the environment, which it stores in the vehicle's memory. The planner reads this symbolic representation, then generates a list of actions to be executed. This architecture offers a major advantage - the addition of planners, such as non-liner planners (described later is this chapter) - which provide the ability to plan several steps in advance to find a solution to more complex problems. Researchers who have conducted the most recent work with these architectures, including Drabble (1993) and Simmons (1990), have concentrated on the execute phase. B. Drabble and R. Simmons strove to detect deviations from planned reactions to sensory input, and to determine at which stage of plan execution process to pass control back to the planner for partial or total re-planning. This endeavour requires the researchers to anticipate all potential problems before they are encountered by the IA V - a difficult, if not impossible task. Some IA V s have been programmed to stop while re-planning occurs. Alternatively, an IAV could be programmed to continuously modify its plans to achieve the goals of an application so that it could respond to changes in sensory information. These proposed solutions likewise require a delay while the re-planning process occurs, causing the modified plan to possibly become obsolete before it is implemented. This latter feature is a major disadvantage with this type of control architecture. The other criticism of this type of architecture is the process of converting sensory data into internal symbolic notations. Researchers such as Brooks (1991b) argue that humans do not process sensory information in this manner (I only wish to note the conectionist V s symbolic argument but not become embroiled in it in any way). In summary, plan-then-execute architectures improved the performance of IA V s by introducing the ability to plan many steps in advance to solve problems. Nevertheless, opponents of these architectures have cited their symbolic approach and the slow speed of a planner's assessment, execution, reassessment and re-planning 8
2.1.3 Subsumption Architecture In the eighties, Rodney Brooks re-kindled interest in the reaction-based method of IA V control by publishing papers outlining the development of subsumption architecture (Brooks 1986; Brooks 1990b; updated version in Brooks 1991a). Brooks designed a layered architecture which enables an IA V to respond to sensory input from an environment with fixed, simple reactions. Brooks and collaborating researchers claim to have improved the reaction-based systems by replacing the traditional AI modularity approach, outlined in Figure 2.5, with a behaviour-based, layered approach, show in Figure 2.6. Sensors I V Perception Manipulate the World Modelling Build Maps Planning Sensors ----> Explore ----> Actuators Task Execution Avoid Hitting Things Motor Control I V Actuators Locomotive Figure 2.5 Figure 2.6 This layered approach entails no implicit separation of data and computation. Brooks implements these architectures as "networks of message-passing augmented finite state machines (AFSMs)". An example of one such network is shown in Figure 2.7. Lower layers in the network take control of the vehicle's actuators by suppressing higher layers in some situations. For example, if an IA V moves too close to an obstacle, the obstacle avoidance procedure takes control and suppresses the output of 9
nfra Sensor und Figure 2.7 The designers of subsumption systems contend that their approach offers at least three advantages over previous models. First, subsumption enables IA V s to function in uncertain environments. The display of this ability by Genghis and Genghis II, robotic ant projects developed at MIT (Brooks 1989), attracted the attention of the popular press (Taylor 1994). While reporters who have highlighted these IA Vs for the public frequently fail to account for the subtleties and limitations of present AI research, Genghis and Genghis II are two of the most high profile applications of this architecture. A second high profile project, the NASA planetary roving vehicle, likewise employs a subsumption-based system to enable vehicles to navigate on uneven, moon-like terrain (Gatt 1993). The adaptability of subsumption may likely arise from the reaction-based design of this architecture. 10
The behavioural competence of the system is improved by adding more behaviour-specifIc network layers to the existing network. This process is called layering. This is a simplistic and crude analogy to evolutionary development. As with evolution at every stage of the development the systems are tested. Each of the layers is a behaviour-producing piece of network in its own right, although is may implicitly rely on the presence of earlier pieces of network (199la: 1229). While one might not discuss the functionality of layered approaches with the same bold confidence as has Brooks, this design nonetheless has provided one of the most successful avenues for the integration of features of the architectures yet developed and widely tested, though this is not to say that the layered approach necessarily will feature in the architectures of the future. The third advantage, according to Brooks, is the absence of an abstracted model of the world represented by symbolic means. Brooks contends that no human created abstraction could accurately mirror the actual world in which an IA V must cope, and hence the elimination of a reliance on symbolic abstraction could permit an IA V to better assess and respond to its surroundings. Even so, a careful reading of Brook's own descriptions reveals that even he has not entirely escaped the need for some symbolic representation, albeit in a lesser quantity than required by some other architectures. The methods for achieving such behaviours as compilation of maps which Brooks describes (1986; 1991a) would require some form of internal representation to be shared between behaviours if they are implemented. Critics of subsumption frequently condemn the occasionally outlandish claims designers have made about this architecture. Beyond rejecting the excesses of the subsumption camp, critics also have highlighted four principal shortcomings of this 11 approach. It was noted that the original architecture described by Brooks (1986) lacked a means of representing time or a time delay, and, second, that there was no way to combine the inputs or outputs of several behaviours. Brooks rectified these two problems in an updated version of this architecture (Brooks 1989a and 1990b). In the revised architecture, Brooks provided flxed duration monostables to deal with time in each of the individual AFSMs. Brooks redressed the second problem by feeding the values of the registers within AFSMs "into a local combinatorial circuit to produce new values for registers or to provide an output message" (1991a: 1229). Additionally, Brooks introduced a behaviour language to describe systems to be implemented in the subsumption architecture (1990a). Two of the principal shortcomings, however, remain. Subsumption architectures still require a predeflned, flxed hierarchy of behaviours which have either a top down or a bottom up order of control. An inflexible hierarchy may suit situations where only a single high level task is required, but the hierarchy has to be reordered for a second high level task. Diverse tasks such as walking or picking up a pencil require different hierarchies of behaviours. A second yet unanswered criticism highlights the inability of IA V s controlled by subsumption to conduct whole sale interpretations of their world at any stage. Not all researchers agree that whole-sale interpretations are needed, but the critics generally concur that the Brooksian design does not facilitate a sufflcient level of environmental interpretation. Although the development of subsumption architectures may have been a good move in the right direction, the continued problems have encouraged some researchers to look at other avenues, detailed in the next three sections. 2.1.4 Combined Architectures Other researchers have attempted to overcome the problems of controlling IA V s by using architectures which combine both the plan-then-execute and reaction based approaches to navigation. Lefevre (1994) details one such experimental architecture designed in Europe, called ALICE. As Figure 2.8 shows, ALICE offers 12
' World modelling /\ I I I I Sensors Figure 2.8 Gat has developed similar architectures for NASA (1993). Nevertheless, this combination of approaches retains some disadvantages of both earlier systems, such as a fIxed order of hierarchical control and the slow speed of sequential world modelling. This dissertation offers a further possibility by combining a high level non-liner planner with a subsumption architecture, an approach not widely reported, if reported at all, in the present literature. 2.1.5 Non Symbolic Methods While many AI researchers may not work with subsumption itself, much present research involves the modifIcation and adaptation of reaction based control architectures. These modifIcations may be grouped into two broad categories: non symbolic methods and self-organising architectures. This subsection considers the fIrst of these general groupings, the non-symbolic methods, which include connectionist approaches and fuzzy logic. Several research groups have experimented with connectionist approaches, that is, the use of simulated neural networks to endow IA V s with the capacity to engage in obstacle avoidance. Cliff et. al. (1992) and Gachet et. al. (1993) provide some 13
• A second major non-symbolic method entails the use of fuzzy logic to produce and regulate behaviours. Some researchers have tested fuzzy logic to implement single behaviours. Beom et. al. (1992), for example, used this method for obstacle avoidance, and Baxter et. al. (1993) applied fuzzy logic to improve IAV navigation. C. Voudouris expanded on the use of fuzzy logic in his MSc dissertation (1993) to permit individual behaviours to serve as inputs for other behaviours. This modification enabled Voudouris to design a layered approach possessing the capacity to combine the outputs of behaviours. An example of this work written in the systems definition language is shown in Figure 2.9. rules begin if dmin NEAR then ObsticalAvoidance if dmin FAR then Goals ObstiacalA voidance begin if dl==VN and d2==VN and d3==VN and d4==VN then Vleft:=NS and Vright:=NS if dl==VN and d2==NE and d3=NE and d4==VN then Vleft:=PS and Vright:=PS end Goals begin if energy <= 20 then go_to_charger if energy> 20 then do_jobs go_to_charger begin end do_jobs begin end end end Figure 2.9 14 The further development of fuzzy logic systems, reported in Voudouris et. al. (1994), has yielded some impressive results. This work has equipped IA V s with the ability to make smooth transitions between the execution of different behaviours. Nevertheless, fuzzy logic systems require a predefined and inflexible ordering of behaviours for the performance of tasks. The Voudouris system in its present design suffers two additional defects; it lacks both internal mapping systems and the capacity to store memory of an IA V's previous movements. As a consequence, IA V s on which a fuzzy logic controller is implemented tend to get stuck in dead ends easily. While both connectionist approaches and fuzzy logic systems have generated some promising results, non-symbolic methods, like the other previously described approaches, would need considerable improvement to facilitate significant advances in IA V research. 2.1.6 Self-Organising Architectures Self-organising architectures have gained prominence since November 1994, during the production of this thesis. Researchers developing this method have sought to empower IA V s to modify their own architectures in response to information gathered from the environment and stored in memory, as well as to interact with human programmers, who act as "parents" or "teachers" for the IAVs. Researchers argue that humans still lack sufficient understanding of their own thought processes to even approximate a model for an IA V to emulate (Lewin 1994). Instead, these researchers have sought to equip IA V s with the ability to design and modify their own architectures (Brooks 1991a). The IAV would gain intelligence through this process of learning. Two groups working in this area of IA V architectures have gained pUblicity in both the scientific media and the popular press. The well funded and high-profile Cog's project of the Artificial Intelligence Laboratory at M.LT. pursues the ambitious objective of "building brains for bodies" or humanoid upper torsos (Brooks and Stein 1993; Lewin 1994). It is difficult to evaluate the success of this project at present, as the majority of published references announce the goals rather than detail the results of 15 this work. The second group, at Sussex University, has developed a neural network IA V control system using genetic algorithms which employ a process of natural selection to choose the more successful modifications for an architecture. The Sussex group has generated some potentially promising results in the area of obstacle avoidance, but, as yet, their work has been implemented only on an IA V simulator and not on actual lAYs (Cliff et. al. 1992)1. The Sussex group has also experimented with a simulated vehicle control architecture which uses visual input (Cliff et. ale 1993; and Harvey et. ale 1994). This latter application has produced very interesting results, though the visual research falls outside the scope of this thesis. Self-organising architectures potentially offer one of the ways forward in IA V control, though a great . deal more work will need to be done which will not necessarily follow on from the two previously described projects. 2.1.7 Summary As the previous sections indicate, the IA V research community has not reached a consensus about the direction that future research should take. Each of the methods discussed, both old and new, has strengths and weaknesses. Different groups favour different varieties of architectures, and some researchers continue to search for new methods. After reviewing this literature, I have reached the conclusion that layered approaches, the flexible ordering of behaviours, and the ability to combine the outputs of behaviours are the most important features to be included in any architecture. 2.2 Mapping Systems My thesis research additionally encompasses a second area, the design of systems which enable IA V s to construct maps of their environment. This next section covers the major topics in this subject area. Additionally, I discuss the directions in which I think this research should be going. IThe Sussex team has recently ported their work onto IAVs, although these results remained unpublished during the production of this document. 16
The maps that were initially used in IA V control systems simulated the way many scientists believe humans draw maps of the world - using a top down cartographic format. For some reason, the computing world calls this format a geometric rather than a cartographic map. An IA V using such a system measures objects in relation to the exact angle and distance from a specific point. In the early work with geometric maps, researchers programmed a pre-produced map into the IA V to aid the navigation of the vehicle. Researchers have subsequently adopted a variety of means to attempt to empower IA V s to produce their own geometric maps based on their exploration of their environment. Experiments soon revealed that the inaccuracy of an IA V's sensors make the task of mapping a room in this way, let alone a world, extremely difficult. Factors such as minor inconsistencies in wheel spin have compounded mapping errors as vehicles have attempted to calculate distances and move to locations recorded on their maps. The occupancy grid mapping system developed by Elfes (Blfes 1989a; 1989b) is one practical example of this type of mapping system. This system converts ultra sound information (which is both noisy and error prone) into a probabilistic map. The system stores this information in a grid format of probabilistic information which allows the IA V to determine if a given spot on a grip contains an object or is free. This system still suffers from positioning problems, as the system uses dead reckoning. 2.2.2 Landmark Mapping More recently, researchers have been looking for an alternative way for an IA V to ascertain its position in a world. One possible method of doing this is by using recognisable objects in the world as landmarks. Currently I have found no papers reporting on systems which create maps of landmarks, but Saburo & Shigang (1993) have developed a system to recognise landmarks from visual input. Other researchers, 17 such as Lazanas & Latombe (1993) and Bonasso et. al. (1993), have designed or implemented systems which navigate either to or between landmarks. 2.2.3 Topological Mapping Topological maps connect several landmarks together. Zimmer and Puttkramer provide a description of this form of mapping (1994b), though during my research, I have not found any articles reporting on its implementation. Figure 2.10 shows an example of a completed map. 
Figure 2.10 2.2.4 Summary In summary, these three types of mapping systems hold promise for future AI research. No doubt, further work will be done in this area. 18
There are several different behaviours which collectively come under the heading of planning systems. This section concentrates on two major types of planners: path planners, which have obvious applications for IA V s; and non-linear planners. This chapter also covers planning to plans, a method of planning in which the details of the plan are determined as they are actually required. 2.3.1 Path Planners Virtually all variants of path planners represent navigable space in a form which, theoretically at least, allows the planner to come up with a plan of action to reach a goal. Early path planners tended to represent the layout of a world as a large grid of lateral and longitudinal lines, called a Manhattan grid, created by the imposition of a grid on a geometric map. Search algorithms used this grid to find the best route to any given location. The vehicle would follow the chosen route to achieve its goal. Zimmer & Puttkamer (1994b) report that Manhattan grids have four major limitations. (I) These grids limit the IA V to select one of only four possible directions for movement. As a result, the vehicle follows a choppy path to a goal. (2) These grids require a very accurate, predefined map of the environment. As a result, the IA V is unable to handle changes in its environment. (3) This method requires extensive time to find a suitable path. To redress this problem, some researchers, such as Scott (1988), have incorporated machine learning into Manhattan grids so that the search planner remembers well used paths. (4) The grid has difficulty representing free space. In the next stage of mapping development, researchers abandoned the simple imposition of a grid over a geometric map and changed the mapping systems so that they would more easily facilitate path planning. Brooks (1983) describes one of these transformed mapping systems, and Kuan (1985) details a refined version. The refined 19
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
