UALR Robotics Design Case Study

2.0 Introduction: The standard solution for obstacle handling in autonomous mobile robotics is avoidance [ 1, 2, 3 , 4, 5, 6]. Obstacle avoidance systems assume that the environment should not be altered or that the robot is incapable of altering it, and therefore the best way to handle obstacles is to go around them [1]. Most real world situations, such as search and rescue, hazardous material clean up, and battlefield reconnaissance cannot effectively be solved by avoidance. In these cases it is preferable that the robot be capable of manipulating obstacles instead of avoiding them. A mobile autonomous robot with obstacle manipulation has the ability to remove an obstacle from its path and continue along a direct route to the objective. This enhances the navigational capabilities of the robot by allowing it to choose a more direct route, and in the case where all routes are blocked by movable objects it creates a solution that would otherwise be unattainable. Autonomous navigation in an area littered with obstacles will be improved by enabling a mobile robot to remove objects from its desired path.

Finding an optimal route requires that many factors be taken into consideration. Pushing an object increases the current drain on the battery. This increased current drain shortens battery life, possibly resulting in loss of power before the target is reached. If an alternate route exists, where driving around the obstacle requires less of the battery then pushing it out of the way, then obstacle avoidance is the better route. In cases where an obstacle blocks the only path to the target, obstacle manipulation remains the optimal choice.

Experiments will be run to illustrate the improvement in capabilities resulting from obstacle manipulation. A comparison, with respect to coverage, of a robot using obstacle avoidance to a robot with obstacle manipulation and avoidance will be made.

Coverage is a measure of how thoroughly a robot explores its environment. Complete coverage path planning is achieved when the robot navigates a path that crosses through every area of its environment. The importance of complete coverage path planning in robotics is further discussed in [7].

2.1 Controller Architecture: In the design of autonomous robots the selection of controller architecture is a key decision. Mataric presents the properties of different types of

controllers in [8]. Planner-based systems are at one end of the spectrum and purely reactive systems are at the other.

Planner-based controllers generally rely on a world model for verifying sensory information and generating the appropriate actions. These approaches let the designer explicitly define the tasks and goals of the system. Uncertainty in sensor data and environmental change can cause problems. These approaches have been criticized for their lack of scalability to the complexity of real world tasks [8, 9].

Reactive systems apply functions that map sensor inputs to actuator outputs. They do not keep internal models of the world. Reactive approaches have better computational efficiency but their inability to dynamically store data tends to result in a lack of optimality and goal convergence [9].

Behavior-based controllers fall in-between the two extremes. Behavior-based systems use basis behaviors as building blocks to achieve higher level of functionality. Basis behaviors are typically reactive but usually are more time extended than purely reactive functions [10]. When the basis behaviors interact with the environment and with each other the higher level behavior that results is called emergent behavior.

Behavior-based controls are popular amongst multi-agent systems due to their scalability. An example of a Behavior-based multi-agent system is the Nerd Herd. The Nerd Herd is comprised of 20 autonomous mobile robots. Emergent behaviors, such as foraging and flocking, were created using the basis behaviors safe-wandering, aggregation, dispersion, and following [10].

Toto, an autonomous mobile robot, implements traditional planning tasks with a behavior-based controller [11]. The emergent behavior, boundary following, is the result of combining the commands coming from the basis behaviors avoid, stroll, align, and correct. Toto is an example of a single agent system exhibiting emergent behavior.

2.2 Behavior Coordination: With behavior-based controllers a method for combining the outputs of the basis behaviors is necessary. Pirjanian gives an overview of current methods used to combine behaviors, which he calls coordination mechanisms [12]. Coordination mechanisms are divided into two categories: arbitration methods and command fusion methods [see Figure 1].

With command fusion methods, control signals from multiple behaviors are combined into a single command. In a voting mechanism, each behavior votes for a desired action, and the action with the most votes is taken. In a system with the basis behaviors wandering, following, and obstacle avoidance, each behavior would vote on a direction to steer the robot. The wandering behavior votes for a right turn, while following and obstacle avoidance vote for a left turn. In this case the voting coordination mechanism would send a left turn command signal to the drive motors.

The superposition mechanism uses a linear combination of the behavior outputs to create a command signal for the actuators. Superposition is used in systems where the command signals are not mutually exclusive. When separate behaviors each generate a desired direction vector, the sum of these vectors is used to steer the robot [see Figure 2].

Arbitration methods select one behavior and give it complete control. The different types of methods are named by their selection process. Priority based mechanisms choose which behavior to give control based on a previously assigned priority level. If a higher priority behavior issues a command signal then the lower priority behaviors relinquish control.

In a state based mechanism the controlling behavior is chosen by examining sensor inputs and selecting the appropriate behavior based on the current state of the system [see Figure 3]. When the state based coordination mechanism selects a behavior it has complete control over the system until another is selected. In these systems the behaviors are usually mutually exclusive.

This project will use a state based arbitration method. An arbitration method is chosen over a fusion method because the commands coming from the basis behaviors are mutually exclusive. State based arbitration is chosen because the transition between behaviors is decided by a change of input variables. The controlling behavior will be selected by considering the currently active behavior of the robot, sensor inputs, and classifier output.

2.3 Obstacle Avoidance: Most work being done in autonomous mobile robotics uses obstacle avoidance techniques for motion planning. In obstacle avoidance, an algorithm steers the robot around obstacles using sensors to locate and avoid the object. These systems are designed to work in indoor environments and safely share their workspace with humans [1].

Potential Field Methods (PFMs) are one approach used for motion planning in obstacle avoidance. Obstacles are assigned outward pointing vectors that direct the robot away from the obstacles. The robot is assigned a target vector pointing from the robot toward the target destination. The robot is steered in the direction of the resultant vector.

PFMs offer the advantages of simplicity and ease of implementation; however, they have some inherent drawbacks. They are subject to trap-situations, which result when the robot encounters a dead-end while bounded on either side. The direction of the steering vector will not turn away from the target to allow the robot to go around the obstacles. One solution to the trap-situation problem is implementing a global planner that detects when a trap-situation has occurred and directs the robot to backtrack and take an alternate route [2].

Closely spaced obstacles present a problem. Even though there may be enough space between obstacles for the robot to pass through, the outward pointing vectors assigned to the obstacles combine into a single vector pointing directly away from the opening.

Another inherent problem with PFMs is oscillation in narrow passages or in the presence of obstacles. This is a result of the system becoming unstable. Koren and Borenstein [2] demonstrate this problem in both modeling and on a real mobile robot. They construct a mathematical model of a robot and its environment. A standard test for controllability, the Routh Stability Criterion, is applied to the model. The test shows instability under certain conditions. These conditions occur when the robot’s mass and velocity are increased. The ratio of the magnitude of the obstacle vectors to the magnitude of the target vector can be tuned to lessen the likelihood of instability.

Koren and Borenstein demonstrate these shortcomings by implementing PFMs on a mobile robot named CARMEL [2]. Experiments were conducted where CARMEL passed through two corridors, of different width, at a Velocity of 0.8m/sec. A disturbance was introduced 4 meters into each corridor. In the wider corridor, CARMEL was able to correct for the disturbance and stability was maintained. In the narrower corridor, the disturbance caused CARMEL to begin oscillating and eventually collide with the wall [see Figure 4].

Veelaert and Bogaerts have developed a sensor system that measures potential fields using three ultrasonic transducers [3]. It produces a vector pointing towards the “gravity center” of the nearest obstacles. The gravity center is derived by assigning a weight to each object. The weight is based on the proximity of the object as measured by the sensor.

The sensor system is implemented on a semi-autonomous wheelchair. The driver of the wheel chair provides a target destination vector with a joystick. The wheelchair is driven through a field of obstacles. The joystick is pointed at the target destination throughout the test. The system successfully avoids obstacles, and the target destination is reached. This solution is only achievable if the obstacles are not spaced too closely; otherwise, the inherent problems associated with PFMs would make it unachievable.

Another obstacle avoidance approach is to provide path planning using fuzzy logic. The fuzzy-logic control system discussed in [4] proposes a two-stage learning algorithm for obstacle avoidance. A learning algorithm automatically generates or fine-tunes membership functions. In the first stage, membership functions are generated using supervised learning. A second stage then uses reinforced learning to fine-tune membership functions. This system was tested in computer simulations. The simulation results showed that a fuzzy rule set was generated, and it was capable of obstacle avoidance.

Reactive systems are used in obstacle avoidance. Reactive systems map sensor inputs to controller outputs. A reactive system that uses a combination of ultrasonic sensors and CCD camera to predict the future position of moving obstacles is demonstrated in [5]. The controller consists of a neural network, which is trained offline using relative-error-backpropagation algorithm. The system is tested on a autonomous mobile robot. The robot is directed down a hallway with both fixed and mobile obstacles. The robot successfully navigates the hallway with no collisions.

2.4 Obstacle Traversal: A more versatile obstacle handling paradigm is obstacle traversal. In obstacle traversal the robot drives over the obstacle. A navigation system that uses imagery data to assess terrain is described in [13]. Characteristics such as slope, discontinuity, roughness, and hardness are interpreted from the imagery data. A fuzzy rules set determines the traversability of a region using these characteristics. A region is classified as having low, medium or high traversablility.

The paper compares the fuzzy rules-based approach to traditional analytical methods that use mathematical functions to assess terrain. The fuzzy logic approach allows terrain to be defined in a natural linguistic way resulting in a system that is less susceptible to errors in terrain measurements; however, the use of fuzzy logic does not alleviate the computational expense of image processing.

To test the systems, images of three different terrains are sent to the fuzzy rules set. A sandy region littered with several large rocks was classified as low traversablility. A sandy region with a few small rocks was rated as medium traversablility. A rough dirt path was rated as high traversablility.

2.5 Obstacle Manipulation: A good manipulation method is pushing. Pushing works well for a variety of obstacle geometries without requiring a specific end-effector. This is beneficial because in an uncontrolled environment the shape of the obstacle requiring manipulation is unknown. The drawbacks to using pushing, such as only being able to move objects in a two dimensional plane, are not very limiting in this application

Lynch presents a mathematical model of the mechanics of object pushing in [14], and he defines stability and controllability for object pushing in [15]. These works focus on the object being pushed. The goal is to control placement of the object in a new orientation or location.

The existing work in manipulation by pushing makes assumptions that are not necessarily true in an uncontrolled environment. It is assumes that the robot is powerful enough to push the object. The possibility that the robot lacks the strength to move the object is not considered.

Much of the work in pushing makes the quasistatic assumption. That is that the object’s motion is sufficiently slow that the inertial forces are negligible when compared to sliding friction [15]. This assumption precludes encounters with objects that will roll or slide away when collision occurs.

2.6 Classification Algorithms: To enable a robot’s control architecture with obstacle manipulation requires that the robot be able to examine an obstacle to see if it can be moved. To accomplish this, obstacles will be classified with respect to how easily they are moved.

A typical application for classification algorithms is text categorization. Text classifiers use statistical approaches such as Sparse Bayes, Naive Bayes, Logistical regression, and decision trees. Different Bayesian classifiers are compared with respect to text classification in [16].

For the purpose of obstacle classification a more applicable topic is the use of classification algorithms to classify physical phenomenon. A system that classifies physical events in a distributed sensor network is presented in [17]. Seismic data is used to distinguish between wheeled and tracked vehicles using three different classifiers. The classifiers are Nearest Neighbor, Support Vector Machine, and Maximum Likelihood Classifier. Sets of seismic data for both wheeled and tracked vehicles are used to test the performance of the classifiers. The Support Vector Machine consistently showed a lower error rate in identifying the vehicles.

A fuzzy rule-based system is used in a classification system for emotion recognition in human speech [18]. Acoustic information is used to classify speech into negative and non-negative categories. Experimental results are reported and the percent error for the different classifiers is compared. The fuzzy rule-based system is shown to provide improved performance over Nearest Neighbor and Linear Discriminant Classifiers.

A fuzzy rule-based system is well suited for use as the classifier in this project. The force sensor used is noisy and imprecise. Fuzzy rule-based systems are capable of handling imprecise and noisy signals. Fuzzy-logic rules allow for the behavior to be defined linguistically instead of mathematically. This is convenient when a precise mathematical model of the event is not available.

Fuzzy rule-based systems are adaptable. By adjusting the membership function, the performance is easily altered without having to change the entire algorithm. New sensors, if they become necessary, can be added to the algorithm with less redesign than other classification schemes would require.

3.0 Background: The control architecture is tested on the J5 robot [see Figure 5]. The UALR Competitive Robotics Team built J5 for the 2001 FIRST robotics competition. It has been redesigned for research work. J5 weighs approximately 130 lbs and is comprised mostly of aluminum. It has a robust differential drive system. Each front wheel is chain driven from a rear wheel, which is direct driven.

The power system uses two separate 12 Volt 17 Amp Hour sealed lead acid batteries. One powers the control logic while the other is dedicated to the actuators. This system provides 30 minutes of drive time under no load, full speed, continuously run conditions [see Appendix A].

The device on the front of the robot, called the wedge, is an inclined plane manipulated by a 4-bar linkage [see Appendix B]. A DC motor directly drives it. The inclined plane is a rectangular plate of 6.35 mm thick aluminum. A strain gauge is bonded to the back of the aluminum plate [see Figure 6]. This sensor measures force present on the front of the wedge.

The control system is based on standard PC technology. It has an AT motherboard and an x86 architecture processor. The ISA bus of the motherboard interfaces with motor controllers, digital IO cards, and an analog IO card. A serial wireless modem connects the robot controller PC to a host PC. The host provides a secure gateway to the Internet.

The operating system is Mandrake 9.2 Linux. Linux was chosen for its stability and ease of customization. The OS is stored on a 512 MB flash drive. This has the advantage of having no moving parts and a very fast access time.

The robot uses openSSH for receiving supervisory commands, monitoring the system and downloading new code. The network link is created using a null modem serial link over a wireless modem. The robot side is configured to automatically begin looking for the serial connection at when it starts the operating system.

The sensors on the J5 robot provide all necessary information for navigation and obstacle classification. The strain gauge provides tactile feedback. The drive system has optical encoders placed on the wheel axles. These provide wheel position, wheel velocity, and wheel acceleration values through registers located on the motor controller card. By comparing actual wheel velocity and the wheel velocity command error in wheel velocity can be derived.

4.0 Theory: In this project a behavior-based controller architecture will be used [see Figure 7]. The architecture is comprised of 3 basis behaviors: wandering, avoidance, and manipulation. A behavior coordination mechanism will switch between these behaviors based on the class data it receives from the classifier and the system state.

Using a behavior-based control scheme, allows for the obstacle manipulation ability to be encapsulated in a basis behavior. This provides modularity so that this ability can be incorporated into future projects. As a basis behavior it may also allow for new types of emergent behavior.

4.1 Coordination Mechanism: The behavior coordination mechanism functions as a supervisory controller. A state based coordination mechanism is used. It switches between basis behaviors, and it generates motor control signals from their output. Each time the classifier changes state or a behavior finishes the coordination mechanism selects a basis behavior.

When the robot is first activated and any time the avoidance behavior sends a finished signal the coordination mechanism places the robot in the wandering behavior. It continues to wander until the force sensor detects an obstacle. Once the obstacle is detected the coordination mechanism switches to a new behavior based on the class of the object [see Appendix C].

When the classifier identifies an object as movable, class A or B, then the manipulation behavior is triggered. The coordination mechanism keeps the manipulation behavior active until a change of class occurs. If the classification is C or D the obstacle avoidance behavior is chosen. Otherwise it remains in manipulation mode.

4.2 Basis Behaviors: A wandering algorithm is used as the default basis behavior [see Algorithm 1]. When in wandering mode the wedge is kept in full down position, which is where the front edge of the wedge is about 1 cm above the ground. The wandering algorithm directs the robot to turn to a random direction and drive straight for a random distance then repeat. The random direction and distance is chosen by software based random number generation. The value generated is scaled such that the turning angle is between 30 and 330 degrees and the distance is between .5 and 4 meters.

Do until forcesensor != 0 //wander until object is encountered//

Wedgecontrol(down); //places wedge in full down position//

srand (time (0)); //seeds the random number generator//

R1=rand(void);

R2=rand(void); //get random numbers for direction and distance//

turnsignal=Turn(R1); //generates motor commands for turning//

control(turnsignal); //send turn command to motor controller//

drivesignal=drive(R2); //generates motor commands for driving//

control(drivesignal); //send drive command to motor controller//

The obstacle avoidance behavior directs the robot to back up 50 cm and then signal the coordination mechanism that it is finished [see Algorithm 2].

The obstacle manipulation behavior directs the robot to place the wedge in the full down position and drive straight forward until the sensor data indicates that the obstacle has stopped
moving [see Algorithm 3].

4.3 Obstacle classification: Obstacles are classified into one of four classes [see Figure 8]. The classes convey how difficult an obstacle is to move. Force sensor and drive system feedback will be used as input for the classification algorithm.

Name	Physical Description	Fuzzy Rule
Class A	Obstacle moves, and no wheel slip occurs	If wheel_velocity_error is small and force_feedback is large then Class is A
Class B	Obstacle moves, and wheel slip occurs	If wheel_velocity_error is large and force_feedback is small then Class is B
Class C	Obstacle doesn’t move, and no wheel slip occurs	If wheel_velocity_error is large And force_feedback is large then Class is C
Class D	Obstacle doesn’t move, and wheel slip occurs	If wheel_velocity_error is small and force_feedback is small then Class is D

5.0 Experiments: The first set of experiments is meant to provide data for use in the creation of the classification algorithm. Experiments are run where collisions with easily moved, difficult to move, and immovable objects are observed. These experiments are conducted without any autonomous code running. The robot is driven under manual control. The force sensor output and drive system feedback are recorded using data logging software.

Once the classification algorithm is coded, its membership functions are fine-tuned. The fine-tuning is accomplished by repeating the previous experiment with the classification algorithm online. The host computer monitors the classifier output in real time. The classifiers membership functions are adjusted until the desired output is achieved.

The field used for testing the autonomous code is a 6.4 by 5.5 meter area constrained on all sides by a sturdy metal barrier. For measurement purposes, the field will be divided into equally sized cells. 4 vertical lines, starting 1.1 meters from the outer wall with 1.1 meter spacing between them, are marked. 4 horizontal lines, starting 1.3 meters from the outer wall with 1.3 meter spacing between them, are marked. This sections the field into 25 cells, with each cell being 4% of the total area [see Figure 9].

In this set of experiments the robot is placed in the field. The field contains easy and difficult to move obstacles [see Figure 7]. Obstacle location is arbitrary; however, it will be recorded so that they can be placed in the same location for each experiment.

To provide a baseline for comparison the robot is activated for 10 minutes with only the wandering and obstacle avoidance basis behaviors online. The coordination mechanism is modified so that any obstacle causes the obstacle avoidance behavior to activate. The number of different cells the robot enters is noted and a percentage of coverage is recorded. This phase of the experiment is repeated 5 times.

The experiment is repeated with the same obstacle placement and time limit, but the controller is fully enabled with obstacle manipulation and avoidance basis behaviors available to the coordination mechanism. The percentage of coverage is recorded. This phase of the experiment is repeated 5 times. The average coverage for the obstacle manipulation enabled controller is compared to the avoidance only controller.

The obstacles are placed in a different orientation, and the previously described set of experiments is run again. This process is repeated several times verifying a consistent improvement in coverage. The ability to manipulate obstacles is shown to improve coverage in this system.

6.0 Future Work: The performance of this system can be further enhanced by adding ultrasonic sensors.

Providing the control algorithm with a greater range of vision will allow for more advanced path planning.

A learning algorithm, used to fine-tune the membership functions of the classifier, would automate the system configuration process. An automated configuration process would allow for quicker implementation on different hardware platforms, or in different environments.

The obstacle manipulation basis behavior and obstacle classifier developed here can be used in future works. Using these technologies, improvements could be made in robot clearing and optimal path planning. This could benefit applications such as search and rescue, reconnaissance, and clean up of hazardous material.

[1] Castro, D., Nunes, U., & Ruano, A. (2002). Obstacle Avoidance in Local Navigation. IEEE

Mediterranean Conference on Control and Automation MED 2002, Lisbon, Portugal.

[2] Koren, Y., & Borenstein, J. (1991). Potential Field Methods and Their Inherent Limitations for Mobile

Robot Navigation. IEEE Conference on Robotics and Automation Proceedings, 2, 1398-1404.

[3] Veelaert, P., & Bogaerts, W. (1999). Ultrasonic Potential Field Sensor for Obstacle Avoidance. IEEE

[4] Ye, C., Yung, N., & Wang, D. (2003). A Fuzzy Controller with Supervised Learning Assisted

Reinforcement Learning Algorithm for Obstacle Avoidance. IEEE Transactions on Systems,

[5] Song, K., & Chang, C. (1999). Reactive Navigation in Dynamic Environment Using a Multisensor

[6] Surmann, H., Huser, J., & Peters, L. (1995). A Fuzzy System for Indoor Mobile Robot Navigation.

[7] Yang, S., & Luo, L. (2004). A Neural Network Approach to Complete Coverage Path Planning. IEEE

Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, 34, 718-725.

[8] Mataric, M. (1997). Behavior-Based Control: Examples from Navigation, Learning, and Group

Behavior. Journal of Experimental & Theoretical Artificial Intelligence, 9, 323-336.

[9] Zielinski, C. (1996). Reactive Robot Control Applied to Acquiring Moving Objects. Proceedings of

The 3rd International Symposium on Methods and Models in Automation and Robotics, 3, 893–898.

[10] Mataric, M. (1994). Interaction and Intelligent Behavior. MIT EECS PhD Thesis, MIT AI Lab Tech

[11] Mataric, M. (1990). A Distributed Model for Mobile Robot Environment-Learning and Navigation.

[12] Pirjanian, P. (1999). Behavior Coordination Mechanisms State of the Art. Institute for Robotics and

Intelligent Systems University of Southern California, Tech Report IRIS-99-375.

[13] Howard, A., Seraji, H., & Tunstel, E. (2001). A Rule-Based Fuzzy Traversability Index for Mobile

Robot Navigation. Retrieved November 5^th, 2004, from http://robotics.jpl.nasa.gov/people/howard/Rulebase.pdf

[14] Lynch, K. (1992). The Mechanics of Fine Manipulation by Pushing. IEEE International Conference

[15] Lynch, K. (1999). Locally Controllable Automation by Stable Pushing. IEEE Transactions on

[16] Eyheramendy, S., Genkin, A., Ju, W., Lewis, D., & Madigan, D. (2003). Sparse Bayesian Classifiers

for Text Categorization. Retrieved December 11^th, 2004 from http://www.stat.rutgers.edu/~madigan/PAPERS/jicrd-v13.pdf

[17] Li, D., Wong, K., Hu, Y., & Sayeed, A. (2002). Detection, Classification and Tracking of Targets in

[18] Lee, C., & Narayanan, S. (2003). Emotion Recognition Using a Data-Driven Fuzzy Inference System

Project Proposal

By Traig Born

University Of Arkansas at Little Rock