Research about sensors
Development of Efficient Obstacle Avoidance for a Mobile Robot using Fuzzy Petri nets
Philip D. Baldoni, Yilin Yang and Seung-yun Kim
Department of Electrical and Computer Engineering The College of New Jersey
2000 Pennington Road, Ewing, NJ 08628, USA (baldonp1, yangy2, kims)@tcnj.edu
Abstract – In the field of autonomously operated robots it is quite common for a form of environment mapping to be implemented. The process of environment mapping requires standby time and processing time. The robot remains stationary and surveys the surroundings, then constructs an environmental representation and determines the appropriate path of travel. This process diminishes the fluidity of robot locomotion, resulting in limited applications. Through the application of fuzzy Petri nets (FPNs) with embedded memory module, an enhanced mapping method was proposed to overcome such a limitation. With the storage and reuse of key information, such as past calculations and decisions made by the robot, time spent in survey and analysis is reduced. Since this approach requires less processing time, the proposed method can be executed while the robot is in motion, continuously looping at frequent intervals. The proposed method brings the benefits of greater movement fluidity while also introducing the ability to navigate in a dynamic environment with less erratic decision making. The modeling and simulation results demonstrated an 8% increase in efficiency.
Keywords-Petri nets, Fuzzy Petri net, Obstacle Avoidance, Modeling and simulation
I. INTRODUCTION In the development of an autonomously operated robot
there are several fundamental procedures vital for successful and appropriate navigation such as, for example, the analysis of environmental variables and attributes, recognition of the system states, and evaluation of the degrees of completion. The analysis of the environment is commonly categorized under environment mapping [8].
The process of environment mapping can take various forms, but there are a few common qualities seen frequently implemented [5]. Environment mapping is often broken down into three principal objectives: scanning surroundings through sensors, analyzing and mapping returned data for use by the robot, and determining the appropriate path of travel. During the application of this procedure, a robot begins stationary until the path of travel is determined. Moving along this path until it is completed, the robot is required to stop and update the environment map through another iteration of the process [3]. Although this method holds opportunity for detailed and accurate mapping of the environment, clear drawbacks can immediately be
established, primarily the lack of fluidity in robot movement. With the necessity to periodically stop and reevaluate the environment and trajectory, efficiency and practical applications are compromised. Furthermore, environment mapping cannot handle dynamic situations, as the process of updating the surrounding conditions is fairly infrequent.
Through the use of the proposed FPN, cycled and executed at a high frequency, a dynamic and continuous obstacle avoidance approach becomes realizable, although the high frequency creates potential erratic behavior. Reaction to slight changes in environmental data at such a rate could cause widely changing responses leading to winding and zigzagged trajectories. To circumvent this issue, the principle of memory has been introduced where a weighted sum of previous and current inputs is responsible for reducing these errors.
This paper will be organized as follows. Section 2 introduces the system definitions and Section 3 discusses the fuzzy Petri net models developed both with and without memory module. Section 4 presents the simulation of the proposed models and discusses the results of the simulations. Finally, the last section is the conclusions of the results.
II. SYSTEM DEFINITION A. Ultrasonic Sensor Array
The development of an obstacle avoidance FPN technique is largely influenced and dependent on the arrangement and type of sensors implemented. Ultrasonic sensors were chosen for their ability to provide accuracy without massive amounts of data.
Figure 1. Sensor array
2016 IEEE 17th International Conference on Information Reuse and Integration
978-1-5090-3207-5/16 $31.00 © 2016 IEEE
DOI 10.1109/IRI.2016.42
265
2016 IEEE 17th International Conference on Information Reuse and Integration
978-1-5090-3207-5/16 $31.00 © 2016 IEEE
DOI 10.1109/IRI.2016.42
265
2016 IEEE 17th International Conference on Information Reuse and Integration
978-1-5090-3207-5/16 $31.00 © 2016 IEEE
DOI 10.1109/IRI.2016.42
265
2016 IEEE 17th International Conference on Information Reuse and Integration
978-1-5090-3207-5/16 $31.00 © 2016 IEEE
DOI 10.1109/IRI.2016.42
265
Furthermore, the 3-meter range is well-suited for the needs of developing the technique and prototype. However, due to the narrow vision of the sensors, 20° at 1.8 meters to 15° at 3 meters, an array of sensors needed to be implemented [10]. It was determined that 3 sensors were needed to return adequate environment data without introducing data sets that are too large. As seen in Fig. 1, a field of view ranging from 60° to 120° can be achieved to detect obstacles the robot is approaching.
B. Fuzzy Petri net Representations Petri nets are one of many great graphical and
mathematical modeling tools, which have high potential for many applications [6]. The application of ordinary Petri nets in modeling robotic systems, process modeling, simulation, and many other engineering applications reap great benefits. Precious time and resources can be saved and the modeling of complicated or potentially dangerous systems can be tested. Although many advantages are apparent, the representation of fuzziness in a precise manner is unaccountable by an ordinary Petri net [4]. In many situations, it is not easy to express data in exact forms. To appropriately express intended data and results, a set of procedures can be applied to fuzzy knowledge [7].
Using FPNs to model obstacle avoidance, it was necessary to determine the fuzzy production rules describing the system and its environment. A fuzzy production rule is a description relating two fuzzy propositions. The equation (1) is the set of fuzzy production rules to be used in conjunction with the proposed methods and FPN model [2]. A more detailed idea of this can be shown, defining R to be a set of fuzzy production rules, for R = {R1, R2, . . ., Rn}. The general form of a fuzzy production rule Ri would be:
������� � �� ������� ����� ( 1 )
where dj and dk are propositions, which may contain fuzzy variables represented by a truth value between zero and one, where zero is not true and one is always true. The certainty factor (CF) of the proposition is represented by �� where �� �������� . This determines the strength of the fuzzy production rule relating dj and dk, where a greater certainty factor denotes a stronger rule.
Representing fuzzy production rules, the generalized Fuzzy Petri net model can be defined by an 8-tuple [1]:
FPN: (P, T, D, I, O, �, �, �), where
P = {p1, p2, . . ., pi} is a finite set of places, T = {t1, t2, . . ., ti} is a finite set of transitions, D = {d1, d2, . . ., di} is a finite set of propositions, �� � ��� � � � �!� "�" ��" " I : � # �$ is the input function, mapping from transitions to
places of input, O : � # �$ is the output function, mapping from transitions
to places of output, � : � # ����� is an association function, mapping each transition to a certainty factor,
� : � # ����� is an association function, mapping each place to a truth value, � : � # is an association function, a bijective mapping from places to propositions.
For modeling the proposed system, FPNs were implemented to follow this structure.
C. Physical response For the proposed system, the robot is limited in physical
response to 6 discrete available actions. This reduces computational complexity and allows the scope of the paper to remain focused on the added benefits of a system with memory module. The first action defined is forward motion, where the robot moves directly ahead until it receives a new instruction. Next are the actions slight right and slight left, where the robot will make a turn in the indicated direction at 22.5°. Left and right will make a 45° turn. Lastly, the final action will be to back up the robot, used for events were no safe trajectory is apparent.
III. FUZZY PETRI NET MODELS A. Development of Models
When developing the Petri net model, many additional features must be included to ensure consistency and proper functionality. For example, in Fig. 2(a), we observe place p1 containing two tokens. Satisfying the weights of both arcs, the path taken by the tokens is nondeterministic, potentially resulting in their separation. However, in Fig. 2(b), place p2 with an inhibitor arc is introduced to regulate which transition fires first. As the number of tokens in place p2 satisfies the weight of the inhibitor arc, it will disable the unwanted transitions. When p2 contains two tokens, transition t1 will always be inhibited, forcing deterministic and desired results.
While the inhibitor arcs are useful for restricting transitions, many cases exist where a transition should instead be enabled given certain conditions. This introduces the need for test arcs, which allow a transition to fire when the weight of the arc is met. Similar to the inhibitor arc, the test arc does not remove tokens from the originating place, a very useful property when attempting multiple comparisons or for preserving the tokens of previous states.
(a) Regular Arcs
(b) Inhibitor Arcs
Figure 2. Controlling the Transition
Fig. 3(a) demonstrates the inability to make multiple comparisons. With enough tokens to enable both transitions one will first fire in a nondeterministic nature. By using test arcs (illustrated as dotted rays) to resolve this issue, both
266266266266
comparisons can be achieved as shown in Fig. 3(b). Although the use of test and inhibitor arcs is fundamental and necessary for the process of modeling the systems, they introduce the undesirable effect of remnant data (i.e., tokens). In most situations, the tokens must be cleared after use to assure the model functions as intended. The solution to clearing a token requires a place to be connected with a dead-end transition that will accept incoming tokens without sending them to a destination place.
(a) Regular Arcs
(b) Test Arcs
�%&'()�*+�,'-.%/-)��01/2(%3043� B. FPN Model without Memory Module
A model for Fuzzy Petri net (FPN) without memory module is developed as shown in Fig. 4 using HPetriSim which is a modeling tool designed to simulate stepwise processes such as Petri nets [9]. The model illustrates three input locations, p1, p2 and p3, one for each ultrasonic sensor. To determine the inputs for simulations, the distance of any obstacle appearing within range of the sensors is recorded and fitted to an input using the function given below.
56789�:� ��;*�������������:� < *=������= > : ? *�������� > : ? =
Place p0 is initialized with a token. The empty place p10 allows the inhibited transitions t1, t2 and t3 to fire, thus accepting the input data, while places p4, p5 and p6 wait for all input data to be grouped before identifying the level of safety.
By running this model, the distances in places p1, p2 and p3, are adjusted to a fuzzy value,���, between 0 and 1 based on the level of safety indicated by the direction as shown in Fig. 5. The fuzzy value is then weighted based on safety by �, through the subset of transitions O: {ti | pj � ti} such that only transition 9� fires where ��> ��. Once weighted values are processed through the model, the final decision for movement is generated. Transition t4 fires in the case of inadequate safety, where ��< �� resulting in the decision to back up. If the safety of the center is very low but the side sensors are safe enough, it results in a left or right turn. If the center is of medium safety and the sides are of high safety, a slight left or slight right turn will result. Lastly, if the safety of the side sensors is not high and the safety of the center sensor is at least of a medium degree, the result will be forward movement as shown in Table 1.
The fuzzy membership functions as shown in Fig. 5 are designed according to the location of sensors. For the left and right sensors, an object is considered 'near' much earlier
than that of the front sensor. This results in the side sensors having a greater sensitivity to objects than the front sensor. This was done so that the navigation would have a forward bias, only turning if necessary.
Figure 4. FPN Obstacle Avoidance Model without Memory Module
Figure 5. Fuzzy membership function for the center sensor (top) and the
left and right sensors (bottom)
Fig. 6 illustrates the preposition based rules. The first three columns of each row represent an individual rule associated with three input sensors (left, front and right). The last two columns for each row indicate the fuzzy modules output represented by the left and right wheel speed, which can be translated into one of the discrete directions (hard left, hard right, etc.). For every proposition
0.5 1.5 2.52 31
Near FarMedium
0.5 1.5 2.52 31
Near FarMedium
0.5
1
0.5
1
Distance
Distance
Sa fe ty
Sa fe ty
0.33
High 0.66
Medium
Low
High
Medium
Low 0.33
0.66
267267267267
each of these blocks displays the value of the respective fuzzy membership function, including the inputs necessitated by the given rule and the resulting outputs. When the fuzzy readings from the sensors are accepted they can be resolved by one of these rules returning a discrete direction for travel. �
Figure 6. Fuzzy Logic Results based on membership functions
Figure 7. FPN obstacle avoidance model with memory
C. FPN with Memory Module The enhanced model with memory module in Fig. 7
introduces new components in the identified region. The system clock can be seen on the right, preventing
the layers of memory from merging values inappropriately. As the system clock un-inhibits the first row in memory, it fires to the next row through transitions t1, t2, and t3, maintaining the original value. However, notice that the transitions have an additional weighted arc sending the value to the summing places p1, p2, and p3. When inputs are received, each layer in memory fills and passes down. As the lower layers in memory are weighted less, these results have less of an impact the further back in time that it occurs. This is intended to resolve slight inconsistencies in input data, resulting in less erratic decisions and sharp turns less frequently.
The memory’s clock with places p4, p5, p6, p7, and p8 are initialized with each state except p8 containing a token. In effect, the transitions of the third layer in memory are uninhibited and the tokens are fired. As this occurs each place is actively inhibiting transition t4, preventing the clock from cycling until the entire layer is empty. The structure of the memory module allows it to determine weighted average while maintaining an adequate level of safety. When deciding to make left or right turns, it will also be less likely to diverge from the ideal path. It should be noted that the memory must be initialized to all values of medium safety so it can reach the required weight value when it is averaged during the probability adjustment. Therefore, any remainder must be cleared before the next summing process begins, which will be signaled to occur as the clock permits it.
IV. MODEL SIMULATIONS AND RESULTS The simulation developed includes a set of nine
coordinates marking the location of the obstacles as shown in Fig. 8. The starting location is the center of the left border and the goal location is any point on the right border. This is due to the omission of destination tracking features, which is out of the scope of memory influenced obstacle detection. Therefore the FPN is structured to prefer forward motion when possible, thus allowing the goal location to be set as anywhere along the right border. Furthermore, the distance of the path taken and the ending location can be compared with the optimal path to better evaluate the FPN’s efficiency.
The simulation graph has the x-axis and y-axis labeled from 0 to 10 and -3 to 4, respectively, in meters. The x-axis also represents the iterations of movement and decision- making. At each iteration, new data are collected, a decision is made, and the robot travels to the next location where the process is repeated. Table 1 contains the inputs recorded for each step and the resulting decision. To produce comprehensive simulations the process uses iterations delimited by the distance traveled in the forward direction,
268268268268
however iterations triggered by time or other units of distance produce similar results.
Figure 8. Simulation results
Matching the specifications of the ultrasonic sensors, the maximum range of detection chosen for this simulation is 3 meters. Additionally, the field of view created by the proposed arrangement of sensors for simulation is the same as modeled in Fig. 1. In this simulation the direction of the robot is always facing in the positive x direction, however the introduction of destination tracking features would be responsible for the adjustment of this parameter.
TABLE 1. SIMULATION RESULTS
x Input Output
w/o mem. mem. w/o mem. mem. L C R L C R
0 3 3 2 3 3 2 SL SL 1 3 2 1 3 2 1 SL SL 2 3 3 1 3 3 1 SL SL 3 1 3 3 1 3 3 SR St 4 3 2 3 3 2 3 St St 5 3 1 3 2 3 1 HL St 6 1 2 3 2 2 3 SR SR 7 3 1 3 1 3 3 HL SR 8 3 3 2 1 3 2 SL SR 9 3 3 1 1 3 3 SL SR
• x: location of the robot in x coordinate • w/o mem: without memory module • mem: with memory module • L: left sensor, C: center sensor, and R: right sensor • SL: slight left turn • SR: slight right turn • HL: hard left turn • St: Straight
The results of the simulation demonstrate that the
model with memory module and influenced inputs not only follows a more direct path but also reveals a less erratic decision making process. Comparing the lengths of the paths taken in Fig. 8 the path followed using memory module is 8% longer than the ideal path, while the path without memory module is 17% longer than the ideal path.
In addition, the decision history in Table 1 demonstrates the decrease in erratic behaviors. The model without memory module is seen making unnecessary hard turns and thus following a jagged and irregular path. Comparatively, the memory module based model does not frequently oscillate between left and right turns, and only uses hard turns when it is deemed crucial.
V. CONCLUSIONS In this paper an alternative to the traditional
environment mapping was proposed. Modeled and simulated using fuzzy Petri nets, the obstacle avoidance capabilities of the proposed method were simulated. Furthermore, it was demonstrated that introducing a weighted memory based on time resulted in better decision making and a more direct path, avoiding unnecessary sharp turns. Simulations of the method running with and without the memory module have shown that the enhanced fuzzy reasoning offered by the module decreased the excessive deviance from the ideal path to only 8% longer than necessary as opposed to 17%.
REFERENCES [1] P. Baldoni and S-y. Kim, “Fuzzy Petri net Modeling and Simulation:
Toward Enhanced Direct Reasoning Algorithms,” Proc. of the ISCA International Conference on Computers and Their Applications, pp. 101-106, 2015
[2] S. Chen, J. Ke and J. Chang, “Knowledge Representation Using Fuzzy Petri Nets,” IEEE Trans. on Knowledge and Data Engineering, 2(3), 1990.
[3] C. Kim and D. Chwa, “Obstacle Avoidance Method for Wheeled Mobile Robot Using Interval Type-2 Fuzzy Neural Network,” IEEE Transactions on Fuzzy Systems, Vol. 23, No. 3, pp. 677 – 687, 2015
[4] S-y. Kim, “Modeling and Analysis of a Web-based Collaborative Enterprise using Petri nets,” Proceedings of the 2008 IEEE International Conference on Information Reuse and Integration, pp. 422 – 428, 2008.
[5] R. Luo and C. Lai, “Multisensor Fusion-based Concurrent Environment Mapping and Moving Object Detection for Intelligent Service Robotics,” IEEE Trans. on Indust. Electronics, Vol. 61, No. 8, pp. 4043 – 4051, 2014.
[6] T. Murata, “Petri Nets: Properties, Analysis and Applications,” Proceedings of the IEEE, 77(4), pp. 541-580, 1989.
[7] S. Reddy, “Fuzzy Predicate Logic for Knowledge Representation”, Proc. of the iFUZZY Intl. Conf. on Fuzzy Theory and Its Applications, pp. 43-48, 2013
[8] M. Selekwa, D. Dunlap, D. Shi, and E. Collins Jr., “Robot Navigation in Very Cluttered Environments by Preference-based Fuzzy Behaviors,” Robotics and Autonomous Systems, Vol. 56, pp. 231 – 246, 2008
[9] HPetriSim, Petri net Modeling Software, Available at: http://www.winpesim.de/default.html
[10] Parallax, Ping Ultrasonic Distance Sensor, Available at: https://www.parallax.com/sites/default/files/downloads/28015-PING- Sensor-Product-Guide-v2.0.pdf
269269269269