Decision Table: if and then Rules.
1. Introduction
The interest in investigating and developing mobile robots is very largely motivated by a need and a desire to have robots that can work with and for people in their normal work. The field of the autonomous mobile robot is a fascinating research topic for many reasons. In this research, some problems associated with mobile robot navigation are identified and described, and the new methodologies are established and verified with real world experiments. The problem description and importance are given in section 2. Numerous behavior rule selection and/or behavior coordination mechanisms can be found in the earlier literatures. Saffiotti A, and Leblanc K (2000) suggest dividing action selection mechanisms into two groups that he calls arbitration and command fusion which correspond to [Mackenzie D.C, Arkin R.C, and Cameron J.M (1997)] state-based and continuous classes respectively. Arbitration or state-based mechanisms are suitable in situations where only a relevant subset of the robot's behavior repertoire needs to be activated in a given state.
Behavior arbitration schemes [Pattie Maes (1991)] emphasized the testing of hypotheses of behavior rather than solving real-life tasks. Konolige, et al [Kurt Konolige, Karen Meyers, and Alessandro Saffiotti (1992),] used fuzzy control in conjunction with modeling and planning techniques to provide reactive guidance of their robot. Computer simulations [Song K.Y. and Tai J. C (1992)] feature a mobile robot that navigates using a planned path based on fuzzy logic. Song et.al.[ Pin F.G(1992 )] presented a scheme for independent control of two drive wheels on their simulated robot. When an obstacle is detected by one of the robot's proximity sensors, the fuzzy controller increases the speed of the respective wheel to turn away from it. Another approach [Arbib M. A (1992)] is more strongly motivated by the biological sciences which appeared on the heels of the subsumption architecture. Arkin [Arkin R. C (1989)] addressed the implications of schema theory for autonomous robotics [Arkin R. C. and D. Mackenzie (1994)]. A neural network [Petru Rusu, Thom E. Whalen, Aurel Cornell and HansJ.W Spoelder (2003)], [C.T. Lin and C.S.G. Lee (1991)] relies on training to relate inputs to outputs. Although observing the weights gives us an idea about the input –output relations, the governing rules cannot be explicitly stated.
The shortcomings of the above approaches are explored and resolved using the proposed approach named as the Alpha Level Fuzzy Logic System (ALFLS).
2. Important
The problems identified for the mobile robot navigation are (i) Behavior rule selection without rule conflict while more than one rule receives equal activation strength as the robot encountered multiple obstacles in the environment and (ii) Finding a near optimal path for the robot to reach the target from the starting point.
In the application of mobile robot navigation in real life situations such as explorations, searching for objects, sign of life in the event of accident and/or natural disasters, etc., the robot is required to navigate and reach the target in the quickest possible time using the shortest path. The capability of AI based control techniques can be used to achieve these types of navigation task. In the fuzzy logic based mobile robot navigation techniques as stated in the literatures in section 1, the input and output fuzzy sets are scaled to larger intervals. As a result of this, the robot deviates from the encountered obstacles much earlier before reaching the obstacles. Due to these situations, the deviations between the robot and the obstacles are quite large. Therefore, the robot takes more time and longer distance to reach the given target position during robot navigation. Also, as the interval of fuzzy set becomes larger, the possibilities of behaviour conflict situations are more. In order to resolve these issues, the proposed methodology ALFLS has been established.
In the proposed method, the environmental perceptual field is well defined by a set of control parameters through alpha level intervals of fuzzy sets. Similarly, the expected control output parameters are partitioned by alpha level intervals. An alpha level threshold is set at each critical fuzzy set and this maximizes the truth value for a particular behavior rule that needs to be fired at a time. In ALFLS, an alpha level makes all the truth membership functions between the threshold intervals to be true and the remaining values to be zero. When an alpha level threshold is applied to the truth of a rule’s predicate, it determines whether or not the truth is sufficient to fire the rule. The effectiveness of ALFLS has been demonstrated through experimental studies using Khepera II Robots.
The effectiveness of the proposed ALFLS is demonstrated through experimental results and analysis and has shown the improved performance as compared with the previous methods in the aspect of (i) the time taken for the robot to reach the given target, (ii) the distance traveled to reach the given target position and (iii) resolving behavior rule conflicts in situations, where the obstacles appear with equal preferences in the environment.
As the outcome of the research, a new deterministic methodology was established and implemented. A comprehensive mathematical framework of decision-making procedure incorporating alpha-level fuzzy logic was established and discussed. The performance of ALFLS was demonstrated using the navigation rules which are obtained by varying the fuzzy intervals such as 3-alpha interval and 2-alpha interval. The comparative results have showed that the 3-alpha interval method has significantly improved the performance with respect to the issues highlighted as objectives.
3. Theoretical work
The behavior rule conflict situation is illustrated in Figure 1. In this illustration, the environment consists of several obstacles which are represented in a fuzzy scale called Small (S), Medium (M) and Big (B) with the measure of (0-2 meters), (2-3.5 meters) and (3.5 –5.0 meters) respectively. In the above environment, there are two obstacles appear in Small fuzzy set (0 to 2 meters) at two different distance ranges as detected by front sensors S3 and S4. Similarly another two obstacles appear in the Medium fuzzy set. In these situations the active navigation rules are presented as below.
If S3 Small and S4 Medium Then Z SN (1)
If S3 Small and S4 Big Then Z SN (1)
If S3 Medium and S4 Medium Then Z Zero (1)
If S3 Small and S4 Small Then Z MP (1)
The activation strength of each rule appears as ‘1’at a particular instant. In this situation, a particular rule needs to be activated. This type of situation is resolved by defining each of the input fuzzy set into alpha-intervals and the limits are established. The corresponding output membership grade is estimated as a truth membership value and referred to as alpha or truth-value.
When an alpha threshold is applied to the truth of a rule’s predicate, it determines whether or not the truth is sufficient to fire the rule. And as a result of single behavior rule activation in the above context, the navigation path must be optimized with minimum deviation from obstacles. When there are no behavior conflicts, the formulation established using fuzzy logic approach [S.Parasuraman, V.Ganapathy, Bijan Shirinzadeh, (2006)] is good enough to navigate in the complex environment. The following section presents the mathematical formulation of ALFLS. The output membership of the navigation system consists of output of normal and behavior conflicting environmental context. The control system chooses the output membership function between the above two contexts based on the maximization of the truth-values. Based on Table 1, the possible rule activations of the present illustration as given in Figure 1 is expressed mathematically and given in Table 2. In this table only two input X1 and input X2 (front sensor data (S1 and S2)) are considered, which are used to detect obstacles that appear in the front region of the robot as illustrated in Figure 1.
C Output |
X_{1,2} | …. | X _{j,2} | X _{1, j +1} | ….. | X _{m, 2} |
X 1,1 | C1,1 | C j,1 | C 1, j +1 | ..… | C _{1, m} | |
…. | ….. | ….. | ….. | ….. | ….. | |
X i, 1 | C i, 1 | C i, j | C 1, j +1 | ….. | C _{1, m} | |
X i +1, 1 | C i +1,1 | C i +1, j | C i +1, j +1 | ….. | C _{i +1, m} | |
…. | …. | …. | …. | ….. | …. | |
X n,1 | C n,1 | C n, j | C n, j+1 | ….. | C _{n, m} |
X_{1,1}, X_{1,2}, ……X_{n,1}, X_{m,2} are fuzzy inputs and C_{1,1} C _{i, 1}, C _{j,1}, ….. C _{n, m} are corresponding fuzzy outputs.
Considering the fuzzy set of the above two sensors, the possible behavior rule sets are shown in the Table.2.
Inputs | Sensor X2 (S2) | ||||
Sensor X1 (S1) | Membership/Output | Small(s) | Medium(M) | Big (B) | |
Small (S) |
0 | SP | SP | ||
Medium (M) |
SN | Z | Z | ||
Big (B) | SN | Z | Z |
The behavior rules shown by row-column (2,10,(2,1),(2,2) and (1,3) cells are conflict rules as discussed in the illustration. The measurement values of input parameters X1 and X2 obtained from the sensors S1 and S2 have to be translated to the corresponding linguistic variables. Normally any reading has a crisp value, which has to be matched against the appropriate membership function representing the linguistic variable. The matching is necessary because of the overlapping of terms as shown in Figures 2 (a) and (b), and this matching is called, coding the inputs or fuzzification.
In Figure 2, the sensor input x1 U1,
Similarly the line passing through x2 intersects only the terms X2i and X2i+1 of X2 giving the crisp values as shown below:
The active rules shown in the Table 2 are redefined and are shown in Table 3 as a generalized formulation to resolve the conflicting behavior rule selection. Four cells in Table 3 contain nonzero terms. These cells are called active cells. Table 3 shows only four rules that are active as illustrated in the present example shown in Figure 1. The rest of the rules will not produce any output.
Inputs | Sensor X2 (S3) | |||||
Sensor X1 (S4) | Membership/Output | |||||
0 | 0 | 0 | ||||
0 | ||||||
0 |
where
In the equation (2), the then part of each rule is called the strength of the rule and the strength is denoted as ‘‘. The strengths
Inputs | Sensor X2 (S3) | ||||
Sensor X1 (S4) | Membership/Output | ||||
0 | 0 | 0 | |||
0 | |||||
0 |
Where
The numbers ij, ij+1, i+1,j and i+1, j+1 are called rule strengths, and are shown in Table.4. Table 4 is similar to Table 3 with the difference that the active cells in Table 4 are the numbers expressing the strength of the rules while the same cells in Table 3 are occupied by fuzzy output. Control output (CO) of each rule is defined by operation conjunction applied, based on the strength of the rules (number expressing the strength) and the fuzzy output and are given as below. This is equivalent to performing max operation on the corresponding elements in the active cells and are shown in the Table 5
Inputs | Sensor X2 (S3) | |||
Sensor X1 (S4) | Membership/Output | |||
0 | 0 | 0 | ||
0 | ||||
0 |
The output of four rules, located in the active cells in Table 5, have to be combined or aggregated in order to produce one control output with membership function agg (Z) as shown below.
The (max) operation is performed on a number and a membership function of an output fuzzy set. Number of linguistic fuzzy set on each sensor input i = j. In this context, the real number and the output membership function C (Z) can be obtained as shown below. A max operation is performed on a number and a membership function of the output fuzzy sets.
The final ith output of the fired rule ’Ci (Z) is expressed as
where
μCi (Z) = max (min ((X1i+1)
3.1. Implementation of ALFLS
The programming procedures are provided in the flow chart shown in Figure 4. In the proposed ALFLS method, a control rule is activated, when the measurement of the obstacle distance exactly matches the rule conditional part (‘if’ part of the rule). Each conditional part of the rule is formulated using the alpha interval fuzzy sets. The final decision made is based on the corresponding action part (‘then’ part of the rule) of the matched rule. In order to match the input data of the sensor with the ALFLS rules, the following control procedures are formulated and adapted for the experiments.
The programming procedures are provided in the flow charts shown in Figure 2.
Consider the first rule, i = 1. Initialize μCo (Z) = 0.
For ith rule, read the membership value of each of the variables in the antecedent part as per the equation 3.
Take the minimum value of step 2, then find the output membership value using the equation 3.
If i = final rule, set μC’ (Z) = μC i (Z) then stop. Otherwise set i = i+1 and go to step2.
4. Experimental investigations
The 3-alpha Intervals: In order to illustrate the capability and performance of ALFLS techniques, the experimental studies are carried out as follows. Firstly, the obstacle distances of the environment from the robot represented by ‘Small’ fuzzy set are well defined by dividing the corresponding distance ranges into three intervals and referred to as 3-alpha intervals. The navigation rules are established using the three alpha intervals and experimental studies are carried out. Secondly, in order to demonstrate the variations of the performance of the ALFLS techniques, the experimental studies are repeated using two intervals of the ‘small’ fuzzy set and are referred to as 2-alpha intervals.
The real world environment consists of real obstacles such as blocks, walls, and curved walls etc., which are situated in an unstructured manner as shown in Figure 5. The experiments were repeated several times in the same environment with the same starting and the target positions and for different alpha intervals.
The behavior rules obtained from ALFLS are fed into the robot control system and the experimental results are obtained and evaluated to show the performance of the proposed methodology. It is observed from the experiment that the robot moves through the optimized path and deviates from the encountered obstacles and reaches the target. The results of the experiments are shown in the graph and given in Figures 6 and 7. These Figures are the graphs showing cycle time plotted against the obstacle distances from
sensors S0 to S7and steering angle. The final path travel is computed from the total control cylce time and the speed of the robot, which kept as same value in all experiements. The near optimal path is achieved by behaviour rule selection using the 3- alpha fuzzy intervals when more than one behaviour rules of the same kind is present in the environment during navigation. A small portion (period around 280 x20 ms, 300 x 20 ms and 345 x 20 ms) of the output results of Figure 6 are enlarged and shown in Figure 7.
As illustrated in Figure 7, the sensor reading shows the obstacles which have appeared at various distances. As defined in ALFLS, these obstalce distances are partitioned as alpha level and the corresponding rule predicates maximizes the truth value for particular rule to be fired in the conflicting sitaution. As a result of ALFLS (3 alpha intervals), the robot deviates from the encountered obstacles with the turn angles deviations from +30 to –20 deg for the entire control cycle. This is illustrated in the enlarged portion of the graph in Figure 6. From the above experiment, it has been observed that due to the 3- alpha intervals used in establishing behaviour rules, the robot deviates from obstacles (as perceived by sensors) in close vicinity and navigate towards the target. The navigation path deviations are as close to as
The significant variations of the results of ALFLS methodology are illustrated by changing the alpha intervals to two ranges (2-alpha intervals) and are discussed in this section. The experiments have been conducted similar to the above method without changing the environment. The range of the input fuzzy set small is changed into two intervals and the corresponding navigations rules are established and tested with experiments. The navigation path in this experiment is shown by a series of Figures 8 from (a) to (f). The experimental results are discussed and shown in Figure 9 and the enlarged portion of Figure 9 is given in Figure 10. It can be seen from the graph shown in Figure 10, that the robot deviations due to the encountered obstacles are more than the deviations illustrated in the 3-alpha intervals while the robot moved towards the target. The robot turn angle deviations are
5. Results and discussions
The effectiveness of ALFLS is demonstrated using the real world experimental results of Khepera II. The comparative results of obstcale deviations from 3 and 2 alpha intervals are shown against the control cycle time in Figure 11. As observed from the graph, the navigation path deviations are as close to
The existing Fuzzy logic approaches used larger interval of input, output fuzzy sets, and build the navigation rules. Due to the larger intervals, the robot turns over wider angle and avoided obstacles during navigation. Some times this also affects the behavior selection, when more than one obstacles are present at the same intervals with two different distances closer to the robot. In this situation the proposed ALFLS is more suitable to map the sensor’s
inputs and behavior rule selection. The graph shown in Figure 12 shows significant improvements using ALFLS than the existing fuzzy logic approaches for mobile robot navigation.
7. Conclusion
The experimental study was conducted to investigate the proposed ALFLS methodology for mobile robot navigation using Khepera II mobile robot. The Experimental investigations show that the proposed formulation reduces the complexity of building the navigation system in a complex environment. The proposed methodology demonstrated improved performance of mobile robot navigation in terms of (i) behaviour rule selection without conflicting (ii) smaller time taken of the robot to reach the target and (iii) the distance traveled to reach the target position, which is shorter compared to the other accepted methods
References
- 1.
Saffiotti A. Leblanc K. 2000 “Active PERCEPTUAL anchoring of Robot Behavior in a Dynamic Environment” Proceedings of the IEEE Int. Conf. On Robotics and Automation (ICRA-2000) SanFrancisco, CA. - 2.
Mackenzie D. C. Arkin R. C. Cameron J. M. 1997 “specification and Execution of Multiagent Missions” Autonomous Robots 4 (1), pg.29 57 . - 3.
Pattie Maes 1991 "A Bottom-Up Mechanism for Behavior Selection in an Artificial Creature,” From Animals to Animats, MIT Press. - 4.
Kurt Konolige; Karen Meyers; Alessandro Saffiotti 1992 "FLAKEY, an Autonomous Mobile Robot," technical document, Stanford Research Institute International. - 5.
Song K. Y. Tai J. C. 1992 "Fuzzy Navigation of a Mobile Robot," Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Raleigh, North Carolina. - 6.
Pin F. G. 1992 "Using Custom-Designed VLSI Fuzzy Inferencing Chips for the Autonomous Navigation of a Mobile Robot" Proceedings of IEEE/RSJ Intl. Conf. on Intel. Robots and Systems, North Carolina. - 7.
Arbib M. A. 1992 “Schema Theory” in the Encyclopedia of Artificial Intelligence 2nd ed. Wiley-Inderscience, pg1427 43 , New York. - 8.
Arkin R. C. 1989 )."Motor Schema Based Mobile Robot Navigation” international Journal of Robotics Research, pg. 92-112l8 - 9.
Arkin R. C. Mackenzie D. 1994 "Temporal Coordination of Perceptual Algorithms for Mobile Robot Navigation", - 10.
Rusu Petru Thom E. Whalen Aurel Cornell Spoelder Hans J. W. 2003 “Behavior based Neuro-Fuzzy Controller for Mobile Robot Navigation IEEE Transaction on Instrumentation and measurement”,52 4 - 11.
Lin C. T. Lee C. S. G. 1991 )“Neural network based fuzzy logic control and decision systems,” IEEE Transaction on Computations.40 pg 120-1336. - 12.
Parasuraman S. Ganapathy V. Bijan Shirinzadeh 2006 ).“Behavior rule selection using α-level FIS for mobile robot navigation during multiple rule conflicts in the complex environments” Inderscience, International Journal of Automation and Control (IJAAC), pg.342-361,1 4