A DECENTRALIZED INTELLIGENT CONTROL SYSTEM FOR AN AUTONOMOUS UNDERWATER VEHICLE E.A. de BARROS*, H. MAEDA*,H. YAMATO** AND S. MIYAJIMA* *Institute of Industrial Science, Univ. of Tokyo. 7-22-1 Roppongi. Tokyo 106. Japan **University of Thkyo,Depanment of Naval Arch. and Ocean Eng., 7-3-1 Hongo,Tokyo, Japan
Abstract. A decentralized control system based on parallel distributed processing is proposed for an autonomous underwater vehicle. Transputers and the Occam language were adopted for the implementation. It i. auempted the use of a parallel object-oriented model for the investigation of coordination ar•.1 cooperat ive criteria among control units. There is free use of sensory-driven responses, and commands based on internal lTh,dels of the environment. These characteristics are combined inside the control units, which exchange infonnations and share per'!JlCCtiives in order to solve problems. The development of this control system related to the problem of navigation and guidance near the sea bed is emphasized. A colision avoidance system based assisted by a grid map has been investigated. and some prehminary resullS of simulations are presented. Key Words . Anificial Intelligence. Distributed Control. guidance SYStems. obstacle avoidance. parallel processing, robots. undersea vehicles.
The research on autonomous underwater vehicles. "AUVs". has been encouraged by recent advances in robotics. particularly in the field of mobile robots. A number of practical applications of AUVs has been proposed. One can mention • for example. cable and pipeline inspections under-ice bathymetric surveys • search for lost objects. oceanic environment research, etc_ The level of autonomy of the vehicle is related with the ability of the inboard control system in taking "reliable" decisions in real-time. Therefore. a complex software system supported by a fast and reliable hardware system is a requisite when designing the control architecture of an AUV. Together with these points, limitation of the available space for hardware, and a desirable fault tolerance of the system motivated the authors to research the use of parallel distributed processing based on transputers for the control system of a mission-oriented AUV. Transputers can form a network that is easily expandable and reconfigurable. Such implementation has been used for preliminary tests of a decentralized cooperative control system . In these tests. the problem of guidance and navigation of an A UV near the sea bed is considered. The path planning is based
on a scenario of the sea bed obtained through an inboard ..o:!ar system. 2. A COOPERATIVE CONTROL SYSTEM An A UV control system. as in any other mobile robot. must perform a number of activities during a given mission. A concurrent approach is a necessity when considering the simultaneous operation of all functions involved in a task that should be executed efficiently by a mobile robot. To drive the vehicle to a given goal point. for example. usually imply in the execution of the following functions : a) Control of actuators and sensors b)Processing and interpreting sensory data (identification of obstacles. for example) c) Building representations of the vehicle relatively to the surrounding environment d) Defining guidance commands Those activities are in some way dependent of each other, they should be interleaved and harmonically combined while the vehicle is in movement. Distributed control systems have been applied to mobile robots for addressing this kind of question. In blackboard-based systems, distributed problemsolvers interact through the sharing of da!a and results in a common data base ( Elfes • 1986; Blidberg and Chappell, 1986; Arkin, 1987; Goto et al.. 1990). In a more decentralized system. the
layered architecture (Brooks. 1986). control modules run asynchronously. and interact through prescribed interference mechanisms on a module's input and output. In Noreils and Chatila (1989). each module has its own shared memory. and communication is done through a multibus.
perform some generic internal functions. like path planning. navigation, etc.. that may use internal models of the environment and vehicle for analysis of situations. before deciding actions according to the mission goals. However. purely sensory-driven responses may also be taken into account depending on the circumstance. A state of emergency (like the subtle detection of a near obstacle, for example) and a lack of enough information for analysis, according to inner models. and decisions on time. may let the sensory-driven responses predominate.
Another possible decentralized system is based on the actor model (Hewitt, 1977; Agha 1987) that motivated the development of some object-oriented languages. This system can be considered a model for a community of experts that work independently but cooperatively. Message-passing mechanisms between modules are used for delegating jobs. exchanging information. and coordinating actions. There is no shared memory. The communication is usually buffered and asynchronous.
The former paradigm was adopted by the authors in order to develop a control system based on distributed parallel processing for an AUV. A distributed system of problem solvers are intended to be developed for specific missions related to the survey over the sea bed. Avoiding bottlenecks present in blackboards and multibus systems is one of the advantages of an actor-like system.
II Main Characteristics
Fig. 1. An example of a decentralized heterarchical control system.
Distributed Control . Control units work most of the time on different aspects of a mission task (see Fig. 1). They form a heterarchical control system. Units can suggest independently commands to other units in charge of the vehicle 's effectors. Decisions are taken based on shared perspectives and cooperative criteria.
Use of Cooperative Criteria. The application of already proposed methods for distributed problem solving. like partial global planning ( Durfee. 1988) and cooperation rules form the main approach for coordination among the control units . Communication Protocols. The efficiency of the whole system depends on information carried by messages. They should be concise and very meaningful. Different kinds of messages should be investigated. A message passing mechanism to be adopted is in part motivated by the model used in the parallel object-oriented language "ABCL/I" ( Yonezawa and Tokoro, 1986).
Unlike a hierarchical control system. the path of commands is not fixed. Different control units may determine course of actions depending on the situation and mission goals. Moreover. there is no command fusion based on prescribed mechanisms. like subsumption in the layered architecture. Information exchanging together with knowledge and rules distributed over the control units are used for deciding course of actions.
Software implementation. The application is running on a transputer network using the language "Occam", whose characteristics of concurrency and communication between processes are explicitly represented. and permits fast execution on transputers. However. Occam presents limitations when compared with parallel object oriented languages. Therefore. in order to permit an objectoriented implementation on transputers. some adaptations are necessary. In the case of
A control unit may be implemented in one or more processors. Communications among processors are performed only by message passing. Combination of Sensory-Driven and Goal-Oriented Actions. There is free use of representations. plans. and behavioral approaches combined inside the control units. They are intended. in principle. to
DAh: asynchronous communication, for example, objects should be mapped in more than one Occam process (Ciampolini et al., 1989; Lai and Foe, 1991). During the implementation of a control unit for the AUV, a dedicated object has been developed for buffering and sending messages, the "mail box" (see Fig. 2). In future, another object related to the management of communication should be developed.
employed by this unit for building wider maps of a site, and locating points of interest according to mission purposes. Nayigator. The navigator integrates inboard and external sensory data for determining the vehicle's position. Global and local path-planning are determined together with the "Mapper" and the "Pilot". This unit also recognizes patterns of motion relatively to the terrain, as for example: "going over the top of a hill", "going into a valley", etc. This feature is intended to be used in the local pathplanning.
Occam is a static language in the sense that it doesn't permit dynamical creation of processes. This problem has been solved in some extent using Occam-like extensions of other languages. like "parallel C". This is probably the most serious limitation of Occam in relation to languages based on the actor model. Despite of this fact, many aspects of a concurrent cooperative control system can be developed and tested using transputers and Occam. From Control
Units and/or Sensors
Units and/or Effectors
module is responsible for guidance and motion control, determining commands to the effectors (thrusters. ruder. and elevators). It performs also the monitoring of the effectors response in the case of long-term missions.
Global aspects of the mission and its schedule are partially and specificaly represented in each unit. 3. A CASE STUDY ON THE NAVIGATION NEAR THE SEA BED
The initial development of the control system has been done together with an investigation on a problem. the sonar-based guidance of a vehicle near the sea bed. Resources to the unit "Pilot". and mapping through the grid representation (Elfes. 1989) have been developed.
Simulations using a model for the motion in the vertical plane of the vehicle "Pteroa 150" (see Fig. 3).were carried out. and the first results are commented in this paper. This cruising type underwater vehicle has been developed at the University of Tokyo. A linear model for a cruising velocity of 1 m/s was considered The only excitation assumed was the force and moment due to the elevators. The surge efforts were neglected, and transfer functions for the pitch angle. and the depth rate were estimated using the analysis of a freemodel test ( Barros et al.. 1992). A linear feedback controller. is used. where the input is the ordered pitch angle. and the output, the elevator angle .
Fig. 2. Basic scheme of a control unit 2.2 Description of Some Control Units A brief functional description of the modules to be included in a preliminary version of this control system can be done as follows : Sonar Operator. The main way for perception of the sea bed is based on the use of ultrasonic beams. The sonar operator guides the beams directions providing active perception of obstacles. It is also responsible for preprocessing and monitoring of the sonar data.
Compared with light and radio waves. sound waves have the least attenuation when traveling through the sea. Particularly in turbid and/or deep waters. the use of cameras for identifying objects is very limited. However. identifying the vehicle surroundings using only ranges and directions given by narrow beams is not an easy task . This is
Mapper. Using the sonar data. and taking into account the vehicle's motion. this unit generates a local map around the vehicle. Such map can be used for local path-planning. A set of local maps are also
the case of the vehicle considered, which is provided with 4 ultrasonic active echo sounders. Beam directions are fixed relatively to the body • and spaced in intervals of 30 degrees, from the forward (coincident with the longitudinal body-axis) to the downward (altitude sensing) directions, as illustrated in Fig. 4.
The minimum altitude assumed was
The values used for the limit in the beam range are 25 meters, and 50 meters. The algorithm is presented in the table 1.
Table 1 Terrain Following algorithm
for i = 2, 3 : if
Fig. 3. Coordinate systems in the vertical plane
where, b max = max
Two guidance algorithms are used by the "Pilot": the line of sight, LOS, and a terrain folIowing algorithm similar to the one proposed by Ishitani et a1. (1989).
(hi =-tan- I (Zj-Zj_)) I (xi-xi_]}), K*bO) A= 20m
b() = -tan-I((RI-ZO)IA),
K =( 3, if RI < zo; I, if R I ~zo) In the LOS algorithm, the commanded pitch angle is given by the vertical plane angle: Scorn
= tan- 1 (Ztarget -Z)
= K* bo
~e = tan- I (b3)
where: X, and Z are the absolute coordinates of the vehicle; Xtarget, and Ztarget are the coordinates of the goal point.
where, b3 =(R)/R4)
The algorithm performance is good in smooth terrains . Neverthless, a serious problem is the difficulty in avoiding abrupt changes in the terrain, like needle type obstacles ( see Fig. 5). The vehicle can not detect the obstacle between the beams. Moreover, once the forward beam detects the obstacle, the vehicle nose turns up. As soon as no more forward obstacle is detected, the vehicle is commanded to follow the terrain, "forgetting" the last event. The vehicle nose turns down again, getting closer to the obstacle. This kind of behavior explains the fluttering of the vehicle in some cases, as can be observed in the graphic of the pitch angle.
Fig. 4. Representation of the acoustic beams, and the piecewise approximation. In the terrain folIowing algorithm , the vertical profile of the terrain is approximated by a piecewise linear curve determined on basis of the intersections of sonar beams with the sea bed surface, as shown in Fig. 4. The algorithm uses the projections of the slant ranges in the body axis "z" :
R4 < limit
An improvement was tried taking into account past detections before deciding maneuvers. For this purpose, a communication between the "Mapper" and "Pilot" was used. A grid representation was adopted for storing the areas scanned by the sonar. A local map built during the maneuver using a terrain folIowing algorithm is shown, as example, in Fig
·6. The white area represents free spaces detected by the sonar. In right side down of Fig.6. some grey points already indicate the presence of the needle type obstacle.
detected obstacle. and pass to the "alert" state; otherwise. the "Pilot" asks to the "Mapper" for the highest obstacle near the detected one. and whether or not free spaces were detected over it. If the
0.1,..._ _ _ _ _ _ _ _ _ _ _ _ _ __
. .... ..... . . . ..... .. .- ....
:s g 02
oZ "().2 «
.. . . ... . . .......... . .... . . . "
Fig. 5." Terrain Following" : Pitch angle and Trajectory
Fig. 7 "Map aided planning" : pitch angle and trajectory
Fig. 6 A local map based on the sonar model
" Mapper "reports that there isn 't enough information on free spaces at the required site, the "Pilot" decides to "look up", invoking the LOS algorithm relatively to the forward obstacle for turning up , and changes to the "attention" state . If enough grid units representing free spaces were detected, the "Pilot" assumes the "attention" state, although it proceeds following the terrain.
An event-driven process of consultation to this map is started by the "Pilot". The event considered is the obstacle detection by the forward beam. The process of path-planning is briefly described as follows: Through its "mail -box", the "Pilot", after requesting, receives readings from the ultrasonic beams, or results on consultations to the local map. Four states during maneuvers can be assumed, depending on the detection of a forward obstacle. In the "normal" state, for example, the vehicle is just trying to track the vertical profile of the sea bed in a constant altitude through a terrain-following algorithm . If a forward obstacle is detected in a "normal" state, two situations may occur : if the slant-range is less than a predefined limit, the "Pilot" guides the vehicle to a constant altitude over the
While new forward obstacles are recognized, the "Pilot" is kept in the "attention" state. Comparison of new forward obstacle coordinates, with values stored in the memory is performed, and a decision of which values are kept in memory is made based on the higher pitch angle calculated by the LOS algorithm. In this state. when no other forward obstacle appears. the free position detected by the forward beam at the "X" coordinate of the obstacle position stored in memory is used as a new reference value. and the state is changed to "waiting" . In the "waiting" state. the vehicle follows the terrain, but the "Pilot" continues to consult the local map, looking for a higher obstacle near the original one . After a limit distance to the stored coordinates is exceeded, the vehicle is commanded for turning up,
and passes to the "alert" state.
Press. Cambridge, MA. Arkin, R. C. (1987). Motor schema based navigation for a mobile robot : an approach to programming by behavior. Proc.of the IEEE International Conference on Robotics and Automation, 264-271. Barros, E. A. de, H. Maeda and S. Miyajima (1992). A system identification experiment for an underwater vehicle. Proc. of the] lth Ocean Engineering Symposium . Society of Naval Architects of Japan. 255-262. Blidberg, D. R. and S.G. Chappel (1986). Guidance and Control Architecture for the EAVE vehicle. IEEE Journal of Oceanic Engineering, vol. OE11, no. 4. 1986. Brooks. R. (J 986). A robust layered control system for a mobile robot. IEEE Journal of Robotics and Automation. 14-23. Ciampolini A.. A. Corradi and L. Leonardi (1989). Parallel object system support on transputer-based architectures. Microorocessing and Microprogramming, 27, 339-346. Durfee. E.H . (1988). Coordination of distributed problem solvers. Kluwer Academic Publishers. Elfes. A. (1986). A distributed control architecture for an autonomous mobile robot. In: "Autonomous Mobile Robots" (S.S. Iyengar, A. Elfes. Eds.). 2, 135-144. IEEE Computer Society Press, CA, U.S.A. Elfes, A. (1989). Occupancy grids : a probabilistic framework for robot perception and navigation. Ph.D. thesis. Camegie-Mellon University. Goto, Y, S.A. Shafer and A. Stentz (1990). A driving control scheme for mobile robots. In : Vision and Navigation. The Carnegie Mellon Navlab, 203-230. Kluwer Academic Publishers. Hewitt. C. (1977). Viewing control structures as patterns of passing messages . Artificial Intelligence Journal, 8, 323-364. Ishitani. H .• Y. Baba and T.Ura. Attitude control system of a streamlined cruising type autonomous submersible. Proc. of the 6th Int. Symposium on Unmanned Untethered Submersible Technology ~, 452-457 Lai S.L. and K.F. Foe (1991). Encapsulated data structures using Occam on the transputer. In : "Applications of Transputer 3" : Proc . of 4th Australian Transputer and Occam User Group Conference ATOUG-4. IOS Press. Noreils ER. and R. G. Chatila (1989). Control of mobile robot actions. Proc. of the IEEE Int. Conference on Robotics and Automation , 701707. Yonezawa. A. and M. Tokoro (1986). Object-oriented concurrent programming. MIT Press.
The vehicle is kept going to a goal over the stored reference point. in the "alert" state. Meanwhile. the reference point is having its position updated by consults to the local map. lfaving just passed over the reference point. the "Pilot" checks once more the local map. before returning to the "normal" state. In most of the cases. before sending the ordered pitch to the controller. the pitch commands given by the terrain following algorithm and by the LOS algorithm are compared. and the maximum value is chosen. The exceptions are the "normal" state (only terrain following). and the cases where forward obstacles closer than the safety limit are detected (only the LOS algorithm is used). Some results, obtained when using this approach are presented in Fig. 7. The performance of the method in a smooth terrain is comparable with that one of the pure terrain following algorithm . The method was also tested in the same steep terrain used before. Comparing Figs. 5 and 7. one can observe that, between the two steep hills, the vehicle goes deeper than in the maneuver using the pure terrain following algorithm .As shown by the pitch angle in Fig. 7, after 100 meters , the vehicle starts to turn up . It proceeds until a value of 0.2 radians approximately is reached, when the vehicle turns down until -0.2 radians. This indicates that, as soon as a free space over the top of a hill was recognized and stored in memory, the vehicle changed to the terrain following mode. An improvement was also achieved in avoiding the needle type obstacle. 4. CONCLUSIONS The idea of a control system based on a parallel object-oriented paradigm was presented. Some characteristics of control units directly related with the problem of local path-planning were discussed .Improvements in avoiding collision with obstacles were observed with the event-driven assistance of a grid map. Investigations on further improvements of the path planning with the use of a sonar array and/or a variable directional beam control are intended. As more control units are developed. problems of coordination and conflict resolution will deserve more attention. 5. REFERENCES Agha, G. (1986). Actors : A Model of Concurrent Computation in Distributed Systems. M.I.T.