This paper focuses on describing the CFill algorithm for rough mereology based intelligent agent path planning. The algorithm updates the methodology of the Square Fill Algorithm by increasing its adaptiveness, adding dynamic neighbour building and proposing a way to deal with dynamic changes to the robot environment, by implementing tree based path planning. The author describes the changes to the original algorithm with example values and their outcomes.
Path planning for mobile robotics is one of the currently most researched
scienti c topics. One of the algorithms currently present for path planning using rough
mereology techniques is the Square Fill Algorithm [
The author tries to challenge the problems and proposes a CFill algorithm, based on the previously mentioned. The changes that were made include replacing the method for creating potential eld neighbours to a dynamic one, adding the narrowing mode described further in the paper and a new way of calculating paths, that tackles the problem of dynamic entities entering the map area.
The idea to implement tree based path planning for intelligent agents was
lately used in works including the Rapidly exploring Random Tree*[
Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
One of the biggest challenges in robotics is to determine the position of the world elements such as robots, obstacles or navigation points like beacons. While using various sensor mounted on the mobile agent, an estimate value is always gathered, due to the probability of inaccurate readings. Those readings are prone to error, because of many environmental and mechanical factors for example: the type of surface, range sensors not picking material uctuations or poor camera resolution qualities. This is where Mereology as a theory can help.
The main scheme of Mereology is the notion of part. Any notion of a part that is given, relates to the idea of containment or partial containment . This means that the robot entering a beforehand speci ed area can ascertain its connection to the area, by a degree. Given the information whether it is connected to the area, overlaps it or is its part, the robot is able to establish its position value more precisely. Given the notion carried out by Rough Mereology - part to a degree, a real number can be retrieved in the range of 0:::1 (value of 1 meaning full inclusion, while 0 - no inclusion) to give a precise description of the element location, compared to the target area.
Rough mereology based reasoning as described in [
X
Considering a planar case of an autonomous mobile robot moving in a 3dimensional environment, hence, spatial objects X; Y are gures assumed concept regions and jXj is the area of X. The rough inclusion (X; Y; r) is applied in the construction of the mereological potential eld. Elements of this eld are square and the distance between them is de ned as
K(X; Y ) = minfmaxr (X; Y; r)g; maxs (Y; X; s)g:
Classical methodology of potential elds works with integrable force eld given by formulas of Coulomb or Newton which prescribe force at a given point as inversely proportional to the squared distance from the target. In consequence the potential is inversely proportional to the distance from the target. The basic property of the potential is that its density (force) increases in the direction toward the target. We observe this property in our construction. We start in our construction with a rough inclusion { a similarity measure formalized in the theory of rough mereology. Its basic construct is a rough inclusion. Rough inclusion is a ternary relation : U U [0; 1] and its primitive formulas of the form (x; y; r) read `the object x is a part to object y to a degree of at least r'. A rough inclusion can be used to induce a distance function as well as primitive relations of elementary geometry: betweenness and nearness.
Geometry induced by means of a rough inclusion can be used to de ne a
generalized potential eld: the force eld in this construction can be interpreted
as the density of squares that ll the workspace and the potential is the integral
of the density. We present now the details of this construction, see also [
The potential eld generation methods called Square Fill Algorithm
introduced by Osmialowski and Polkowski [
First of all, the potential eld neighbours are now created dynamically. Instead of eight neighbours at set positions as in the Square Fill Algorithm, the algorithm speci es a neighbours variable, that holds the number of neighbours that should be created around the potential eld (at equal intervals). This is achieved by calculating the angle in radians as following: where n is the selected number of neighbours to be created. The angle is multiplied each time a new neighbour is created in an iteration i, until the total angle remains smaller than 2 radians. To calculate each neighbour position (x0; y0) with a distance d from the potential eld (x; y) the following equation is used: =
350 neighbours
180 x0 = sin( i) d
x y0 = cos( i) d + y (1) (2)
Secondly, the generated potential eld is sparse in open spaces and gets more dense between obstacles. Variable named narrowing distance was proposed to achieve that. Whenever it is set, the algorithm checks the distance between the current potential eld and all obstacles and goes into the narrowing mode whenever the distance is smaller than narrowing distance. The narrowing mode has two tools that can be used for creating a more dense potential eld: creating more neighbours around a potential eld or decreasing the step size for smaller distances. Ideally both tools should be used to t through narrow passages. An example of this method can be seen on Fig. 2. The CFill algorithm is composed of the following steps (pseudocode can be seen in Algorithm listing 1): 1. Set the following variables: { neighbours - contains how many neighbours should be created, { step - the incrementation step distance between potential elds, { radius - the radius of the created potential elds, { goal - position of the goal for the algorithm, { potential f ields - list to store created potential elds, { narrow distance - distance to activate the narrowing mode (optional), { narrow step - increment step distance for narrowing mode (optional), { narrow neighbours - neighbours in narrowing mode (optional). 2. Create an empty queue Q, 3. Set the is clockwise variable to True, 4. Add the rst potential eld at the goal location with a distance of 0, 5. Enumerate through all potential elds in Q, 6. Check the conditions, if any is True, remove the potential eld from Q and go to next potential eld: { Check, if the potential eld is out of bounds of the map, { Check, if a potential eld at that location is already created, { Check, if the potential eld isn't overlapping an obstacle. 7. If the narrowing mode is set and the potential eld is in the distance of narrow distance to obstacle: { Create neighbours with number narrow neighbours and narrow step for distance incrementor from the potential eld as described above, { Add the neighbours to queue Q, 8. If the narrowing mod is not set or the potential eld isn't in the distance of narrow distance to obstacle: { Create neighbours of the potential eld with the number neighbours and step for distance incrementor as described above, { Add the neighbours to queue Q
Algorithm 1 CFill Algorithm
Making the potential eld sparse in CFill algorithm compared to the Square Fill Algorithm required implementing a new way of calculating paths. The previously used method of picking neighbours by selecting new path points by nding the nearest mereological distance between connected potential elds can't be used in CFill algorithm at most times. The proposed algorithm for path planning is devised of two steps: creating possible paths tree and selecting a path, based on navigation to the tree root. 4.1
Below are the steps taken to build a tree graph on the generated mereological potential elds. An example of a proposed tree can be seen in Fig. 3. 1. Append the goal position to the working f ields list, 2. Set the tree radius parameter responsible for determining how far should the algorith look for neighbouring potential elds, 3. Enumerate through the created potential eld list until all potential elds have their parent parameter set, 4. Check the following condition for enumerated eld: { Potential eld distance is smaller or equal to tree radius, { Potential eld is not in the working f ields list, { Potential eld does not have the parent parameter set.
After the tree is generated, a path for the autonomous agent can be chosen. This means following the steps: 1. If the robot is at the goal position - end algorithm, 2. Add the robot position to path points list, 3. Find the mereological potential elds closest to the agent start position and set it to 4. Do the following, until the full path is constructed: { Add the current potential eld position to path points list, { Get the parent parameter of the potential eld and assign it to current. 4.3
After the path points are acquired the author uses a smoothing method modi ed
for rough mereology path planning algorithms presented in [
yk = yk + (xk yk) (3) (4) { The value of the path point is updated, if the distance from the point to any obstacle is greater than the computed collision distance. In other cases, the value remains the same. 4.4
Due to the nature of the proposed path planning method, contraty to the Square Fill Algorithm, it is possible to use the generated path system for dynamic environments, without recalculating the potential eld and/or the proposed path. When a new obstacle is added after the initial calculations, the potential elds in the vacinity get blacked out by setting their active parameter to F alse. The e ect of this is that all branches of the path tree starting or going through that point are turned o . From this point, nding a new path is similar to initial nding of the path as described above - an active point closest to the current robot position is searched for and a new path is selected. 5
The CFill algorithm is the successor to the Square Fill Algorithm proposed by
Osmialowski and Polkowski in [
This manipulation allowed the implementation of the narrowing mode, which gives the possibility of creating more dense potential elds around obstacles, while making them sparse in open terrain - greately reducing the memory needed to calculate the mereologic potential eld.
Moreover, due to how the algorithm created potential elds, the old way of implementing path nding was deprecated. A new solution was presented using tree graphs that were based on the earlier created potential elds. The greatest advantage of this, is that the algorithm is now valid in a changing environment, since adding new obstacles after the path tree was created, does not induce the need of recalculating the whole potential eld or generated paths.
Future work will include further dive into the subject of using CFill in changing environments and bigger comparison of the algorithm with other rough mereology based ideas. More work can be done in the eld of the path tree creation as only one method was tested on how to pick branch roots for the mereological potential eld.