Analysis of Mobile-Robot/Environment Interaction by Y. Koren, Professor and J. Borenstein, Assistant Research Scientist Technical Report No. UM-MEAM-89-1 January 1989 A Progress Report for the Period 12/88 to 1/89 for Department of Energy Grant DE-FG02-86NE37969 C:\WS2000\REPORTS\VEAM1.REP, January 16, 1989 * Page-1

1. Introduction We have implemented the VFF algorithm on a Real-time obstacle avoidance is one of the key commercially available CYBERMATION K2A issues to successful applications of mobile robot mobile platform. The CYBERMATION has a maxi(MR) systems. All MRs feature some kind of colli- mum travel speed of V =0.78 m/sec and weights sion avoidance, mechanisms that detect an obstacle (in its current configuration) about W=125 kg. This and stop the robot in order to avoid a collision. platform has a unique 3-wheel drive (synchro-drive) These include bumpers with microswitches or that permits omnidirectional steering. simple ultrasonic range sensors. Obstacle avoidance represents a much higher level of sophistication, We have equipped this mobile platform with a where the robot is able to detect and detour ring of 24 ultrasonic sensors and an additional comobstacles. This task is much more complex, since it puter (a PC-compatible single board computer, involves not only the detection of an obstacle, but running at 7.16 MHz), to control the sensors. also some kind of quantitative measurements con- Similar sensor configurations have been designed cerning the obstacle's dimensions. Once these have for other mobile robots, such as (Denning, 1985). been determined, the robot has to steer around the obstacle and resume motion toward the original target. Autonomous navigation represents the highest................................................. level of MR performance. Autonomous navigation, Target in general, assumes an environment with known and unknown obstacles, and it includes global path planning algorithms (Borenstein and Koren, 1986a) to; plan the robot's path among the known obstacles, as, Obstacle..: well as local path planning for real-time obstacle \ avoidance... Based on our previous mobile robot experience 4 with the "Nursing Robot" (Borenstein and Koren, /... ostacle 1985; 1986a, 1986b, 1987a, 1987b), we developed a 3 ':.. new and powerful algorithm, entitled the Virtual Ia 1 lallsJ Force Field (VFF), that allows real-time obstacle) \ avoidance at high speed. In this algorithm, obstacles start.................... are represented as occupied cells in a grid. Each. cell's count represented as a certainty value C(ij),.. _ [. which indicates the measure of confidence that an.............. 4X obstacle exists within the cell area (a concept introduced by Moravec, 1986). In our algorithm, each occupied cell exerts virtual repulsive forces onto the Fig. 1: mobile robot, and the target location generates an Robot run with actual ultrasonic data obtained in attractive virtual force. The vectorial sum of all vir- real-time during the robot's motion. Maximum tual forces provides the instantaneous steering com- speed = 0.78 m/sec and average speed = mand tp the robot The idea of obstacles applying 0.53 m/sec. repulsive forces is known as the Potential Field concept (Khatib, 1985). The novelty of our VFF method lies in the combination of Certainty Grids for The complete mobile system, including the VFF alobstacle representation and Potential Fields for gorithm, is denoted as CARMEL (Computer-Aided steering command generation (Borenstein and Robotics for Maintenance, Emergency, and Life Koren, 1988b) as well as the implementation of the support). combined real-time application in a dynamic system. The VFF method has been found to be especially ef- Fig. 1 shows a typical run of the robot with actual fective in compensating for the shortcomings of ultrasonic data, obtained in real-time during the ultrasonic sensors (Borenstein and Koren, 1988a). robot's motion. The robot ran at a maximum speed In addition, the VFF method also compensates for of 0.78 m/sec and achieved an average speed of the dynamics of a fast running robot as we have 0.53 m/sec. demonstrated on a real mobile robot running at 0.78 m/sec (Borenstein and Koren, 1988c). C:\WS2000\REPORTS\MEAM1.REP, January 16, 1989 Page-2

The maximal range for the sensors was set to parameters n, F0, and Ft affect the distance between 2 m, which is why only pan of the rightmost wall is the MR and the scanned object as well as the shown, whereas the rear wall and most of the smoothness of the MR motion. leftmost wall remained undetected. Note that the objects gradually emerge on the computer screen, as One problem associated with the VFF algorithm the robot moves. Each dot in Fig. 1 represents one occurs when the MR has to pass between closely cell with a Certainty Value (CV) unequal to zero. spaced objects or through a narrow passage or corCVs are color-coded on the computer screen, but ridor. In our experiments we observed a tendency of this can not be reproduced here. the robot to oscillate in such cases. The situation illustrated in Fig. 2 shows simula2. The Need for Adaptive Control tion results of our mobile robot traveling in a wide (case a) and a narrow (case b) corridor. In the wide As was mentioned before, the VFF algorithm is corridor, a sudden change in the width causes the based on the balance between a virtual attractive robot to smoothly adjust its path. In the narrow corforce F pulling the MR to the target and a repulsive ridor, however, the sudden change excites the robot virtual force Fr generated by the obstacles. The into unstable oscillations. This example shows that equation of the repulsive force is given by with the VFF method the mobile robot and the environment are becoming one close system, and r,JF, therefore changes in the environment might change Fr =. (1) the stability of this system. In order to guarantee, J i dn stability, parameters in the VFF algorithm must be self-tuned to the environment's level of clutter. where F0 and n are constants (currently, we use n=2), rf. is a unity vector directed from cell (i,j) The objective of this Technical note is to formuto the robot, and d.. is the distance between the MR late the differential equation that describes the inand cell (ij) on the grid. teraction between the mobile robot and the environment This equation will be needed as the model for adaptive control algorithm that will become part of the extended VFF method. y Teat e Targetrget 3. The Differential Equation for the MR/Environment For the analysis of the MR/Environment interac2 | I \ I tion we assume that the robot moves at the middle Object Obect of a long passage. At point Y=0 a pertubation takes the MR to the right by a small distance x. The VFF.// b -- ^ —z~fe ^ I pushes the MR back to the left. We want to explore _tll.5 ~ | I I ^the behavior of the MR/environment interaction system. Path a: wide ' b: narr The simplest model for the MR steering motor is L 7 as r ir a first-order differential equation tr + W = n (2).i... where wt is the actual steering-rate and Q is the corSimulation results with our mobile robot travelling re s is the actual Te at and l is theco in: a. a wide coridor b. a narrow corridor responding command. (The actual relationship is in:a.awidecorrir___________________________ more complicated than the one represented in Eq. 2, since it also includes a corrective network in the steering controller). The steering-rate command is The distance by which the MR travels alongside i or te an obstacle is determined by the resultant Fr as well as the (constant) attraction force Ft. Thus, the = K (6 - 0) (3) C:\US2000\REPORTS\MEAM1.REPo Jauary 16, 1989 Page-3

where 8 is the required steering angle and 0 is the The velocity component of the MR in the actual steering angle, both measured from the X-direction is given by Y-axis. Again, the calculation of nf in our system is more complex, but in principle Eq. 3 is correct. Sub- X = Vs iO =- VO (11) stituting Eq. 3 and ) = w into Eq. 2 yields the steering equation combining Eqs. 10 and 11 yields r0 + 0 + KO = K6 (4) N (12) We designate the magnitude of the lateral repulsive force acting on the MR at Y > 0 as F'. We By differentiating Eq. 4 and substituting Eq. 12 sive force acting on the MR at Y > 0 as Fr'I. We defin a le const rx. h into the resultant equation the interaction model define a lateral constant Frx =C(i,j)F, which is oti,,_,,-,., rx ~ ' J/.0 MR~environment for long passages is obtained: equal for the left and right wall, assuming constant C(i,j) for all obstacle-filled cells. The total repulsive 'r + 0 + KO + NVo = 0 (13) force on the MR consists of two components, one generated by the left wall (at an average distance The characteristic equation of the Laplace transL+x) and the other by the right wall (at an average form of Eq. 13 might be written in the following fordistance L-x), since we assumed that the MR moved mat: accidentaly to the right). (s+a) (s2 + 2twns +W2) = 0 (14) _. _ ^ Fx Frx The damping factor E at the natural fequency wo F rx L+x) n (L-x) n m Eq. 14 depend on the term N in Eq. 8, which, in turn, depends on L - the distance between the MR and the scanned object (i.e., the environment). where Fr and n are constants (currently we use n=2)- The damping of this differential equation is smaler when the distance L to the obstacles is Assuming that L > X, Eq. 5 yields smaller. Therefore, the narrower the passage beomes, the more jerky and oscillatory the MR mopF = ' _ x ( 6 ) tion will become. This is a dangerous situation in a a Jx LJ+1 dcluttered environment, and it can be remedied by which means that the MR is pushed back to the left. applying adaptive control. The required steering angle is calculated by tan 6 = _-_ = -Nx (7) 4.Conclsions It was shown that the MR and the environment where F is the target directed attractive force (in arebeha a a complete syst fornavigation the Y-dir&tion) and with the VFF algorithm. When the level of obstacle dutterness increases, the damping of this system F rx n (8) decreases, and the MR might oscillate and collide N Ft= -L - ( n+1 with obstacles. with To remedy this situation, an environmentadaptive control method is needed for the VFF alF gorithm. With this adaptive concept, the parameters f = xF (9) K (Eq. 13) and f (Eq. 9) will be self-tuned according t to the MR/object distance L, with the goal to maintain a constant damping factor. Since motion is almost parallel to the Y-axis, the angle 6 is small, and Eq. 7 yields 6 = -Nx (10) C:\WS2ZOOO\REPORTS\MEAM1.REP, January 16, 1989 Page-4

5. References Borenstein, J. and Koren, Y., 1985, "A Mobile Platform For Nursing Robots". IEEE Transactions on Industrial Electronics,Vol. 32, No. 2, pp. 158-165. Borenstein, J. and Koren, Y., 1986a, 'Optimal Path Algorithms For Autonomous Vehicles." Proceedings of the 18th CIRP Manufacturing Systems Semi, nar, June 5-6, Stuttgart. Borenstein, J. and Koren, Y., 1986b, 'Hierarchical Computer System for Autonomous Vehicle". Proceedings of the 8th Israeli Convention on CAD/CAM and Robotics, December 2-4 1986, TelAviv, Israel. Borenstein, J. and Koren, Y., 1987a, 'Motion Control Analysis of A Mobile Robot". Transactions of ASME. Journal of Dynamics, Measurement, and Control. Vol. 109, No. 2, June, pp. 73-79. Borenstein, J., Koren, Y., and Weill, R., 1987b, "Hierarchically Structured Multisensor System for an Intelligent Mobile Robot". CIRP Annals, Vol. 36/1, 1987. Borenstein, J. and Koren, Y., 1988a, "Obstacle Avoidance With Ultrasonic Sensors.' IEEE Journal of Robotics and Automation., Vol. RA-4, No. 2, pp. 213-218. Borenstein, J. and Koren, Y., 1988b, 'High-speed Obstacle Avoidance for Mobile Robots.", 3rd IEEE International Symposium on Intelligent Control, August 24-26,1988, Arlington, Virginia. Borenstein, J. and Koren, Y., 1988c, "Real-time Obstacle Avoidance for Fast Mobile Robots". Submitted for publication to the IEEE Transactions on Systems, Man, and Cybernetics, 1988. Denning Mobile Robotics, Inc., 1985, 'Securing the Future". Commercial Offer, 21 Cummings Park, Woburn, MA 01801. Khatib, O., 1985, "Real-Time Obstacle Avoidance for Manipulators and Mobile Robots." 1985 IEEE International Conference on Robotics and Automation, March 25-28, St. Louis, pp. 500-505. Moravec, H. P., 1986, "Certainty Grids for Mobile Robots." Preprint of Camrnegie-Mellon University. The Robotics Institute, Technical Report. C:\US2000\REPORTS\MEAM1.REP, January 16, 1989 Page-5