Path planning of mobile robot by mixing experience with modified artificial potential field method

Abstract

In this article, a new method is proposed to help the mobile robot to avoid many kinds of collisions effectively, which combined past experience with modified artificial potential field method. In the process of the actual global obstacle avoidance, system will invoke case-based reasoning algorithm using its past experience to achieve obstacle avoidance when obstacles are recognized as known type; otherwise, it will invoke the modified artificial potential field method to solve the current problem and the new case will also be retained into the case base. In case-based reasoning, we innovatively consider that all the complex obstacles are retrieved by two kinds of basic build-in obstacle models (linear obstacle and angle-type obstacle). Our proposed experience mixing with modified artificial potential field method algorithm has been simulated in MATLAB and implemented on actual mobile robot platform successfully. The result shows that the proposed method is applicable to the dynamic real-time obstacle avoidance under unknown and unstructured environment and greatly improved the performances of robot path planning not only to reduce the time consumption but also to shorten the moving distance.

Introduction

During the past two decade, robotics has been developed rapidly. Many researchers put their attentions on the navigation of mobile robots. The most basic technology of navigation is path planning which is going to find a safe and efficient way from starting point to target. In recent years, research on path planning has focused on local searching in dynamic environments, where the pose and location of the obstacles are unknown or partially unknown.

A well-known approach to localize the path of mobile robots is artificial potential field (APF) method, ¹ which is used commonly in real-time collision avoidance and smooth path for mobile robots because of its elegant mathematical analysis and simplicity. However, its inherent defects are obvious. First, Robot cannot reach the target nearby the obstacle. The obstacle repulsion increases and gravity decreases rapidly when target point is within the influence scope of obstacle. Second, there is a local minimum problem; when robot is in the process of traveling, the direction of total force and the movement direction of planning path are on the same straight line, and robot cannot avoid obstacle effectively but vibrates back and forth in a certain range. A lot of researchers have proposed some improvements on the traditional APF method in recent years. In 2003, MC Lee and Park ² proposed an improved APF method using a virtual obstacle concept. A virtual obstacle is located around local minimums to repel the mobile robot. This method is adaptable for a real-time path planning because of its lower complexity. However, it is not suitable for the discrete modeling of the mobile robot in complex situation. In 2009, S Charifa and Bikdash ³ presented an adaptive boundary following algorithm guided by APF to avoid the local minima. When the size of obstacles is large, too much computing time need to be taken to guide the robot. In 2011, Q Li et al. ⁴ improved the APF method by providing an additional force and developing the virtual local minimum. The genetic algorithm was introduced to optimize the parameters such as the revolved angle of repulsion. The proposed method could plan out a simple, smooth, and safe path by simulation experiments, but not be applicable to the real world. In 2012, L Guan-chen et al. ⁵ integrated APF approach with receding horizon control method. An additional control term was added in path planning to escape from local minima of APF. This term accomplishes the description of specified property index except for distance and control energy, but the computational process is complicated. In the same year, Q Song and Liu ⁶ presented a dynamic fuzzy APF method to overcome the shortcomings of APF method. Through taking the advantage of velocity vector, modifying the potential field force function, and integrating with the fuzzy control method, all those steps could achieve adjusting the factors of repulsion potential field in real time. However, inputting the fuzzy control method increases the planning time greatly, and in practical applications, the impact of acceleration should be considered.

Moreover, several artificial intelligence algorithms such as fuzzy logic, ⁷ neural networks, ⁸ and genetic algorithm ⁹ have been proposed for the mobile robot navigation problem in unknown environments. The varied information of the environment needs to be detected by sensors to help the robot avoid obstacles autonomously. Those algorithms could achieve optimal local path planning, but they are relatively complex, time-consuming, and not very useful for real-time applications.

In fact, one of the main issues for mobile robot to navigate in uncertain environment is the lack of prior information. If environmental information could be acquired before path planning, it would contribute to guide the robot moving from the starting point to the target. Case-based reasoning (CBR) ¹⁰ is a technique that can reuse previous experience to obtain the suitable information to solve the current problems. Actually, CBR has been used in robotics to perform different tasks for many years. In 2003, Kruusmaa ¹¹ presents a global navigation strategy for autonomous mobile robots in dynamic environments. CBR is used to store those solutions and their outcomes for a later use. It can improve the performance of the robot in a difficult uncertain environment, while is not efficient in simple dynamic environments. Moreover, the restrictions of this approach are that the size of the environment and the position of the goal points have to be known precisely, and the localization errors have to be small (just like it is with outdoor applications with global positioning system (GPS)). Urdiales et al. ¹² in 2006 proposed a sonar-based purely reactive navigation technique for mobile platforms which was relied on CBR algorithm. CBR is used here to let a robot learn how to react in any given situation, so that it can adapt itself to any configuration or environment. However, this system is a purely reactive scheme, its case base can only be trained and learnt by human intervention or other high-level planner system in advance to realize autonomous path planning and does not have the ability to self-learning by its own build-in basic case base. Hodál and Dvořák ¹³ in 2008 combined CBR with graph algorithms, which is represented by a rectangular grid. It is applicable to the large-scale environments, saving computing time and traveling distance; nevertheless, the process is too complex to reduce the efficiency of the algorithm. To sum up, CBR technique can improve the performance of path planning for mobile robots in complicated environments, while the efficiency and applicability are different when CBR has been used in different platforms.

In this article, we proposed a new method which combines CBR method with the modified artificial potential field method (MAPF); we call it “EMMAPF” (experience mixing with modified artificial potential field method). In CBR, we innovatively consider that all the complex obstacles are retrieved by two kinds of basic build-in obstacle models (linear obstacle and angle-type obstacle). Meantime, the self-learning process also stores the past experiences into case base to rapidly generate an effective solution to solve the current problem in path planning when similar situations exist. “MAPF” method is utilized as a basic method to offer basic paths for the case base. ¹⁴ No matter in simple situations or in complicated environments, this method always guides the robot with an optimal path. In section “‘EMMAPF’ method,” a detailed description of “EMMAPF” method is represented, including the modified APF method and CBR technique. In section “Experiment,” we tested our algorithm on a mobile robot by simulating in MATLAB and real test in physical environment. Finally, we summarize the conclusion and future plan.

“EMMAPF” method

In this section, a detailed description of “EMMAPF” method is represented, including the modified APF method and CBR technique. By retrieving and adapting past problems from the case base, we can obtain the solution for current problem; this method can not only help the robot to avoid the obstacles autonomously but also save the computing time and traveling distance to obtain an optimal path.

The procedure of “EMMAPF” method is shown as above (Algorithm 1).

Algorithm 1:

“EMMAPF” algorithm.

When the sensors have detected the obstacle

{ Return the relevant information about the obstacle

Retrieve the similar case from the case base by using nearest neighbor method.

If there is a similar case/are similar cases in the case base

{Return the similar case/cases. If number of the returned cases is greater than one.

Revise the cases to find the most similar case Cp.

Accept the solution Sp of Cp

{Reset the transferring direction.

Calculate the cost r(Pp). It stands for the speed of the robot using CBR to avoid the obstacle.}

}

Else

{Invoke the “MAPF” method to solve the current problem. Find the solution Sm to avoid the obstacle.

Calculate the cost r(Pp). It stands for the speed of the robot using “MAPF” method to avoid the obstacle.

}

Case learning

{If there is no similar case in the case base.

{Store the new case, its solution, and r(Pp) }

Else

{ if r(Pp) < r(Ppold)

{Update r(Pp)}

}

}

}

When the existence of obstacles around the robot is detected by sensors, some related information would be returned to system. After sorting and calculation, it will retrieve the similar cases from the case base based on those attribute datum. If the returned solutions are more than one, select the closest case, and then reset the transferring direction. Otherwise, the system will invoke the “MAPF” method. Finally, evaluate the proposed solution by the cost r(Pp) and update the system by learning from the case base. Thus, in CBR system, learning and adaptation are through accumulation of cases.

“MAPF” method

The traditional APF method is commonly used in real-time obstacle avoidance and smooth path for mobile robots. It is particularly attractive because of its elegant mathematical analysis and simplicity. However, there exists a local minima problem, and no optimization process is involved. Liu et al. ¹⁵ have proposed a concept of virtual obstacle to solve this problem. The virtual obstacle is located around local minimums to repel the mobile robot. We make some improvements based on this approach, modify the potential field force function, and set the virtual obstacle according to the shapes of obstacles detected by the sensor. The steps are shown as follows.

Modify the potential field force function

The attractive force function is described in formula (1)

$$F_{\mathrm{att}}\left(X\right)=-\mathrm{grad}\left[U_{\mathrm{att}}\left(X\right)\right]=k(X-X_{\mathrm{goal}})$$

(1)

where $k$ is the attractive force factor and $(X-X_{\mathrm{goal}})$ represents the distance from robot to the target.

The repulsive force functions are described in formulas (2)–(5)

$$F_{\mathrm{rep}}=F_{\mathrm{rep}1}+F_{\mathrm{rep}2}$$

(2)

$$F_{\mathrm{rep}1}=\eta (\frac{1}{\rho }-\frac{1}{{\rho }_0})\frac{1}{{\rho }^2}{(X-X_{\mathrm{goal}})}^n$$

(3)

$$F_{\mathrm{rep}2}=\frac{n}{2}\eta {(\frac{1}{\rho }-\frac{1}{{\rho }_0})}^2{(X-X_{\mathrm{goal}})}^{n-1}$$

(4)

$$F_{\mathrm{rep}}=\{\begin{array}{cc}\hfill F_{\mathrm{rep}1}+F_{\mathrm{rep}2}\hfill & \hfill \rho \le {\rho }_0\hfill \\ \multicolumn{1}{c}{0}& \hfill \rho >{\rho }_0\hfill \end{array}$$

(5)

where $\rho$ is the shortest distance between the position of the robot and obstacle, ${\rho }_0$ is the radius of obstacle sphere of influence, $\eta$ represents the repulsive factor, and $n$ is a real number greater than zero. Contrast with the original potential field function, it introduces the relative distance between the target and the robot $(X-X_{\mathrm{goal}})$ , ensuring the whole potential field minimum only existing at the target point $X_{\mathrm{goal}}$ . Thus, the gravitational potential field is always greater than the repulsive potential field, till the robot reaching the target point, the potential field of gravity and repulsive then reduced to zero.

The total force is described in formula (6)

$$F_{\mathrm{all}}=F_{\mathrm{att}}+\sum _1^m{F}_{\mathrm{rep}}$$

(6)

where $m$ is the quantity of the obstacles. The total force will help system to solve the target non-reachable problem with obstacle nearby.

Set the virtual potential field area

While the robot gets trapped in a local minimum, it will stop there or repeat the same route back and forth in a certain range. There are two cases of local minimum shown in Figure 1.

Figure 1.

Two cases of local minimum: (a) local minimum case 1 and (b) local minimum case 2.

In 2009, Dr Lei ¹⁶ proposed a new method which increases a special virtual potential based on the original repulsion field to solve this problem. They used a combination method to push the robot away from the local minima. Based on this method, we set the virtual potential field area as the shaded part in Figure 2. When the robot encounters the local minima, take the target point as the center, and calculate the radius R by equation (7) as the virtual potential field area

$$R=\max (\mathrm{distance}(X_{\mathrm{obs}1},X_{\mathrm{goal}}),\mathrm{distance}(X_{\mathrm{obs}2},X_{\mathrm{goal}}))+{\rho }_0$$

(7)

where $X_{\mathrm{goal}}$ represents the target point, $X_{\mathrm{obs}1}$ and $X_{\mathrm{obs}2}$ represent the endpoints of the obstacle, and ${\rho }_0$ is the influence distance of the obstacle. During this part, the robot travels along the border of the obstacle. Figure 2 shows the effect of the modified APF method. Until the robot travels out of the shaded area, the virtual potential field area will be revoked.

Figure 2.

“MAPF” method to solve the local minimum: (a) local minimum case 1 and (b) local minimum case 2.

CBR technique

CBR is a self-learning method which helps to solve the current problem by re-using past cases and experiences to adapt to the changes in the environment. This method is based on the concept that similar problems have similar solutions. The innovation of our proposed CBR algorithm is that the cases of complex obstacles can be retrieved by two basic build-in case models which composed of “linear obstacle model” and “angle-type obstacle model.” Three steps can represent a simplified description of our CBR technique: retrieving the most similar case or cases, revising the proposed solution, and learning and retaining the new case for future problem solving. The flowchart of CBR technique is shown in Figure 3.

Figure 3.

Flowchart of CBR technique.

Case representation

When using CBR technique to achieve path planning for mobile robots, the first fundamental decision to be made is how to establish a case base. Cases can be stored in many different representational formats, ¹⁷ such as framework representation, object-oriented representation, and predicate representation. Because of its features of applicability, summarizing, structuring, and reasoning, we choose framework as the representational format. A classical case base usually includes characteristic of the problem and the relevant solution that was used on an earlier occasion when a similar situation was encountered. A case can be described as follows

$$\mathrm{CaseBase}=〈C1,C2,C3,\dots ,\mathrm{Ci}〉$$

(8)

$$C=〈F,S〉$$

(9)

where $F$ represents the features of the obstacle and $S$ represents the relevant solution

$$\begin{array}{c}\multicolumn{1}{c}{F=〈\mathrm{caseID},\mathrm{obstacleCategory},\mathrm{leftDistance},}\\ \mathrm{rightDistance},\mathrm{angle},\mathrm{rightAngle},\mathrm{flag}〉\hfill \end{array}$$

(10)

where

• caseID: identifier of the obstacle;

• obstacleCategory: the category of the obstacle’s front shape where the sensor could scan, such as line, convex polygon, concave polygon, and so on;

• leftDistance/rightDistance: the length of the obstacle. If the obstacle category is linear, rightDistance will be set as zero;

• angle: the global angle of the obstacle/the angle between two sides. Angle ranges between 0 and π;

• rightAngle: the global angle of the right border. rightAngle ranges between 0 and 2*π. While the obstacle category is linear, rightAngle will be set as zero;

• flag: each situation has two transferring direction, flag = 0 represents the direction of right, flag = 1 represents the left direction, flag describes which direction would be better for the current situation

  $$S=〈\mathrm{resetDirection}〉$$

  (11)

• resetDirection: the transferring direction for the robot.

If the obstacle category is linear, the function of the transferring direction is as follows

$$\mathrm{resetDirection}=\{\begin{array}{cc}\hfill \mathrm{angle}+\mathrm{flag}*\pi \hfill & \hfill 0<\mathrm{angle}<\pi /2\hfill \\ \multicolumn{1}{c}{\mathrm{angle}+(!\mathrm{flag})*\pi }& \hfill \pi /2<\mathrm{angle}<\pi \hfill \end{array}$$

(12)

Else, if the obstacle category is angle-type, such as convex obstacle or concave obstacle, the transferring direction is

$$resetDirection=\{\begin{array}{cc}rightAngle+flag*angle& 0<angle<\pi \\ rightAngle-flag*angle& \pi <angle<2\pi \end{array}$$

(13)

Method of representing case base on Extensible Markup Language

Extensible Markup Language (XML) is a user-defined markup language, which is a set of specifications created by World Wide Web Consortium (W3C) and designed to transport and store data. It is a new generation of web language that uses tree structure, adapts for multi-subsystem architecture in case base, and would be able to describe the relationship between the data.

XML language has good data storage format, is high-structured, and is easy for network transmission, compared with traditional relational databases; the expansibility and reusability of XML are better.

CBR is an incremental and sustainable self-learning process. For retrieving and re-using the previous case, it needs to constantly update the case base. Using XML technology to establish a CBR case-base system has the following advantages:

• Due to a unified data format, standard XML supports the exchange of data between different data sources, so the system can solve the same case in different areas of shared problems, to achieve distributed storage and retrieval of cases.

• XML processing can be independent of the data, so the case can be handled by the other XML applications and also easy to restructure the flow of information between the CBR system and other systems.

There are three aspects to indicate the case:

• Case category: to classify case and build index, be convenience for retrieving;

• Case character: it is used to describe character of the case, distinguish the differences between cases;

• Case solution: make out the solution for the cases.

Empirical formulas

Our Robot is a three omni-wheel mobile robot. We set the simulation model based on iRobot Open Source project. In simulation environment, complex obstacle is constituted by two kinds of basic obstacle models; the empirical formulas are described as below.

Linear-type obstacle

In the open source project of iRobot, obstacle is represented by $\mathrm{wall}=(x_1,y_1,x_2,y_2)$ , where $(x_1,y_1)$ and $(x_2,y_2)$ represent the two endpoints of the obstacle. The variables with smaller x value will be put on the left side, which is compared with intermediate variable wall_idx. If x is equal, then the variables with smaller y will be placed on the left side.

If the type of obstacle is linear, each parameter value of the obstacle in case base is described as below:

• $\mathrm{obstacleCategory}=0$ , it means a linear obstacle;

• $\mathrm{leftlength}=\sqrt{{(x_1-x_2)}^2+{(y_1-y_2)}^2}$ ;

• $\mathrm{rightlength}=0$ ;

• $angle=compute\_direction((x_2-x_1),(y_2-y_1))$ .

where $\mathrm{compute}\_\mathrm{direction}$ represents the direction angle, which is computed by an arctangent function.

When the robot encounters a linear obstacle, the direction of movement is determined as follows

$$dist1=\sqrt{{\left(x_1-x\right)}^2+{\left(y_1-y\right)}^2}+\sqrt{{\left(x_1-x_{goal}\left(1\right)\right)}^2+{\left(y_1-x_{goal}\left(2\right)\right)}^2}$$

(14)

$$dist2=\sqrt{{\left(x_2-x\right)}^2+{\left(y_2-y\right)}^2}+\sqrt{{\left(x_2-x_{goal}\left(1\right)\right)}^2+{\left(y_2-x_{goal}\left(2\right)\right)}^2}$$

(15)

where $(x,y)$ represents the current coordinate of robot, $(x_{\mathrm{goal}}(1),x_{\mathrm{goal}}(2))$ represents the target point coordinate. Move direction is determined by the value of $\mathrm{dist}1$ and $\mathrm{dist}2$ . If the value of $\mathrm{dist}1$ is smaller, flag = 1, then the robot will turn left; otherwise, flag = 0, the robot will turn right.

Deflection angle formula is shown in equation (12). It is a kind of way to walk along the wall when robot encounters a linear obstacle.

Angle-type obstacle

Similarly, angle-type obstacle is composed of two walls with one angle. $\mathrm{wall}(1)=(x_1(1),y_1(1),x_2(1),y_2(1))$ , $\mathrm{wall}(2)=(x_1(2),y_1(2),x_2(2),y_2(2))$ . If it is not a straight wall, put the coordinates of left point on the left side; otherwise, put the point with smaller value of y to (x₁, y₁).

Each parameter value of the obstacle in case base is described as below:

• $\mathrm{obstacleCategory}=1$ ;

• $\mathrm{leftlength}=\sqrt{({(x_1(1)-x_2(1))}^2+{(y_1(1)-y_2(1))}^2)}$ ;

• $\mathrm{rightlength}=\sqrt{({(x_1(2)-x_2(2))}^2+{(y_1(2)-y_2(2))}^2)}$ ;

• $\mathrm{angle}=|(\mathrm{compute}\_\mathrm{direction}((x_2(2)-x_1(2)),(y_2(2)-y_1(2)))-\mathrm{compute}\_\mathrm{direction}((x_2(1)-x_1(1)),(y_2(1)-y_1(1))))|$ . When the robot encounters an angle-type obstacle, the direction of movement is determined as follows

$$\mathrm{dist}1=\sqrt{{(x_1\left(1\right)-x)}^2+{(y_1\left(1\right)-y)}^2+({(x_1\left(1\right)-x_{\mathrm{goal}}\left(1\right))}^2+{(y_1\left(1\right)-y_{\mathrm{goal}}\left(2\right))}^2)}$$

(16)

$$\mathrm{dist}2=\sqrt{{(x_2\left(2\right)-x)}^2+{(y_2\left(2\right)-y)}^2+({(x_2\left(2\right)-x_{\mathrm{goal}}\left(1\right))}^2+{(y_2\left(2\right)-x_{\mathrm{goal}}\left(2\right))}^2)}$$

(17)

Here, the point of intersection will be replaced with $(x_2(1),y_2(1))$ when two walls intersect together. It means that $(x_2(1),y_2(1))$ , $(x_1(2),y_1(2))$ , and the point of intersection are the same.

If $\mathrm{dist}1$ is the smaller one, flag = 1, robot moves along the left wall; otherwise, flag = 0, robot moves along the right wall. Deflection angle formula is shown in equation (13).

When the robot is contacting with the corner of the two walls, there are two scenarios need to be considered, that is, whether to do circular motion around the corner or directly flee away. The velocity vector is decomposed into two orthogonal components. One component along with the line from the corner to the robot. If the intended velocity of the robot has a component directed from the corner to the robot, then it will drive away directly. The other situation is when the component is directed from robot to the corner, the robot will do a circular motion around the corner. The radius of the circular motion is set equal to the radius for avoiding the obstacle.

The other complex obstacles are made up from these two basic types. We need to set up more different obstacles to train the robot and save better paths into the case base. When the robot moving automatically, it will search the case base first, find the matching case, which just need to match the parameters including obstacle type, left length, right length, and the global direction, and then select one of the most similar cases to control the movement, finally get the deflection angle and direction.

Cost function

In order to measure the cost of problem solving, all the cases are characterized by a cost function to calculate the robot consumption in obstacle avoidance. It depends on the mean traveling speed of the robot from encountering the obstacles (the time is Ts) to escaping from the influence of the obstacles (the time is Tg). The faster the robot can avoid the obstacles, the better the solution is

$$r(\mathrm{Pp})=\mathrm{Speed}(\mathrm{Ts},\mathrm{Tg})=D\frac{(\mathrm{Ts},\mathrm{Tg})}{(\mathrm{Tg}-\mathrm{Ts})}$$

(18)

When the robot encounters an obstacle, r(Pp) will be generated to accumulate the distance and time of each step until the robot gets rid of the influence of the obstacle. A solution is selected with a lower cost.

Case retrieval

Case retrieval is always the key part in CBR technology and directly impacts the overall performance of the algorithm. Case retrieval mainly contains three processes: identify the characteristics, preliminary matches, and best selection. First of all, analyze the problem and extract relevant characteristics, identify a set of candidate cases related to the current case from the case base, and finally select one or more cases of the most relevant to the current case from the candidate case. The most commonly investigated retrieval methods by far are the k-nearest neighbors, ¹⁸ artificial neural networks, ¹⁹ knowledge-guided approaches, and inductive index approaches. ²⁰

Because of the number of cases to be searched in our case base is small, we choose k-nearest neighbors as our retrieval method, by computing the distance between the current case and each case in the case base, the closest one will be found as the best solution.

Case retrieval is closely related with the case representation. Weighted average method is a simple similarity measure method for those case bases, which is represented by attribute-value method. The sum of all feature weightings on a case is equal to 1.

In many situations, different features have different levels of importance and contribution to the success of a case, so a reasonable weight needs to be set to reduce the searching space for the case retriever. Considering the number of feature size, we choose a method of rough estimate to assign weightings.

For a given case

$$F=〈caseID,obstacleCategory,leftDistance,rightDistance,angle,rightAngle,flag〉$$

(19)

The retrieval process carries through the following steps:

• Step 1. Search the cases that have the same category with the present one in the case base, $C_i\in \mathrm{CF}$ . That means retrieve cases with the same “obstacleCategory” characteristic attributes. Through this way we can greatly reduce the quantity of matching cases and improve matching speed.

• Step 2. Calculate the distance between current case $\hat{C}$ and case i according to the different feature attributes. $D(\hat{C},\mathrm{CFi})$ represents partial similarity; the smaller the distance, the higher the similarity is. A similarity formula can be defined in formula (20)

$$D(\hat{C},\mathrm{CFi})=\mathrm{abs}(\hat{C}-\mathrm{CFi})$$

(20)

• Step 3. Calculate the sum of multiple distances with weighting factor of each feature, which is the total distance between current case $\hat{C}$ and case i; it is global similarity. Distance formula is defined in equation (21)

$$\mathrm{Distance}(\hat{C},\mathrm{CFi})={(\sum _i{W}_i*D{(\hat{C},\mathrm{CFi})}^2)}^{\frac{1}{2}}$$

(21)

where formula (21) is the most common type of distance measure called Euclidean distance.

• Step 4. We can get the similarity between the two cases according to the definition of given distance

$$\{\begin{array}{cc}\hfill \mathrm{SIM}(\hat{C},\mathrm{CFi})=1-\mathrm{Distance}(\hat{C},\mathrm{CFi})\hfill & \hfill \mathrm{Distance}(\hat{C},\mathrm{CFi})\in [0,1]\hfill \\ \multicolumn{1}{c}{\mathrm{SIM}(\hat{C},\mathrm{CFi})=\frac{1}{1+\mathrm{Distance}(\hat{C},\mathrm{CFi})}}& \hfill \mathrm{Distance}(\hat{C},\mathrm{CFi})\in (1,+\infty ]\hfill \end{array}$$

(22)

When Distance = 0, SIM have a maximum value of 1, which means that the two cases are identical. When Distance = 1, SIM have a minimum value, which means that the two cases are different completely. It indicates that the larger the SIM value is, the more similar the two cases are.

• Step 5. Select one or more cases whose feature is most similar to the current case, arrange those cases in a descending order according to their similarity, the similarities of all those cases are greater than a given threshold value.

For the case retriever, it is reasonable to use weights to calculate the distance between target case and each case in the same category. When it is a linear obstacle, the leftlength’s $W_1$ is defined as 0.2 and the angle’s $W_2$ is defined as 0.8 because linear obstacle’s global perspective is a more important. In the same way, when it is an angle-type obstacle, the leftlength’s $W_1$ is defined as 0.1, the rightlength’s $W_2$ is defined as 0.1, and the angle’s $W_3$ is defined as 0.8. After many test experiments, our team proved that the values which were described above are the best choice. This method is under the influence of people’s subjective consciousness relatively.

Case adaptation

When the case retrieval is completed, we need to adapt the solution to fulfill the needs of the current case. If returned similar cases are more than one, compute the length according to the positions of the robot and the first reset goal to obtain the closest one. If necessary, modify the solution. The pseudo code of case adaptation is shown as above (Algorithm 2).

Algorithm 2:

Case adaptation.

num = number(retrieved case/cases);

count = 1;

If (num > 1)

shortest = Distance of the first retrieved case;

For i = 2 to num

If Distance(i) < shortest

shortest = Distance(i);

count = i;

End

End

Return case(i);

Else

Return case(1);

End

If shortest > 5

Modify the turning direction according to the current case.

End

Update r(Pp).

Case learning and case retaining

Case learning takes an important part in CBR system, which involves the policies and techniques of adding, deleting, and updating cases in a CBR system in order to guarantee its ongoing effectiveness and performance. In this part, case learning is measured by the cost introduced above. Cases with lower cost can play a positive role in the decision making.

If there is no similar case in the case base during case retrieval, the system will invoke MAPF to solve the current problem. The new case, its relevant solution, and r(Pp) will be retained into the case base. It not only increases the coverage of the case base but also reduces the distance between an input vector and the closest stored vector.

In addition, after case adaptation, the solution may be modified in order to adapt to the current environment.

If $r(\mathrm{Pp})<r(P{p}^{\mathrm{old}})$ , update the cost to have a better learning process. What’s more, if the size of the case base is greater than a setting value, some useless cases will be rejected to keep the efficiency of the system.

Experiment

In this section, we demonstrate some simulations and actual tests to verify the efficiency and accuracy of our method. In order to facilitate our actual test, the robot is depicted as a hexagon in the simulation. First of all, the kinematical structure of the robot is described in the following subsection.

Kinematical model

The experiments are implemented using the three omni-wheel robot. The omni-wheel robot could move in any direction. Figure 4 shows the robot.

Figure 4.

Omni-wheel robot.

Kinematical equation can be obtained from its kinematical diagram described in Figure 5.

Figure 5.

Kinematical diagram of the omni-wheel robot.

In Figure 5, ${\left[\begin{array}{cc}\hfill X_a\hfill & \hfill Y_a\hfill \end{array}\right]}^{\mathrm{T}}$ is the world coordinates, ${\left[\begin{array}{cc}\hfill X_r\hfill & \hfill Y_r\hfill \end{array}\right]}^{\mathrm{T}}$ represents a moving frame with respect to the center of the robot, $\theta$ is the rotation angle which is positive in the counterclockwise direction, L is the distance between the robot and the center of each wheel, and ${\left[\begin{array}{ccc}\hfill V_1\hfill & \hfill V_2\hfill & \hfill V_3\hfill \end{array}\right]}^T$ stands for the translational velocity of each wheel.

After reasoning, V_i of each wheel can be obtained and described in the vector–matrix form as follows

$$\left[\begin{array}{c}\hfill V_1\hfill \\ \multicolumn{1}{c}{V_2}\\ \multicolumn{1}{c}{V_3}\end{array}\right]=P\left(\theta \right)·\left[\begin{array}{c}\hfill {\stackrel{·}{X}}_a\hfill \\ \multicolumn{1}{c}{{\stackrel{·}{y}}_a}\\ \multicolumn{1}{c}{\stackrel{·}{\theta }}\end{array}\right]$$

(23)

where

$$P\left(\theta \right)=\left[\begin{array}{ccc}\hfill -\sin (\theta +30\circ )\hfill & \hfill \cos (\theta +30\circ )\hfill & \hfill L\hfill \\ \multicolumn{1}{c}{-\sin (30\circ -\theta )}& \hfill -\cos (30\circ -\theta )\hfill & \hfill L\hfill \\ \multicolumn{1}{c}{\cos \theta }& \hfill \sin \theta \hfill & \hfill L\hfill \end{array}\right]$$

(24)

In fact, the velocity of each wheel has been given in advance. We can obtain the orientation and speed of the robot through another equation transformed by equation (25)

$$\left[\begin{array}{c}\hfill {\stackrel{·}{X}}_a\hfill \\ \multicolumn{1}{c}{{\stackrel{·}{y}}_a}\\ \multicolumn{1}{c}{\stackrel{·}{\theta }}\end{array}\right]=P^{-1}\left(\theta \right)\left[\begin{array}{c}\hfill V_1\hfill \\ \multicolumn{1}{c}{V_2}\\ \multicolumn{1}{c}{V_3}\end{array}\right]$$

(25)

where

$$P^{-1}\left(\theta \right)=\left[\begin{array}{ccc}\hfill -\frac{2}{3}\sin (\theta +30\circ )\hfill & \hfill \frac{2}{3}\sin (\theta -30\circ )\hfill & \hfill \frac{2}{3}\cos \theta \hfill \\ \multicolumn{1}{c}{\frac{2}{3}\cos (\theta +30\circ )}& \hfill -\frac{2}{3}\cos (\theta -30\circ )\hfill & \hfill \frac{2}{3}\sin \theta \hfill \\ \multicolumn{1}{c}{\frac{1}{3L}}& \hfill \frac{1}{3L}\hfill & \hfill \frac{1}{3L}\hfill \end{array}\right]$$

(26)

Simulation

Based on kinematical equation described above, three different obstacle cases which retrieved by the proposed two basic build-in case models have been designed to run the experiments, respectively, including one linear obstacle, one concave polygon obstacle, and one convex polygon obstacle. In order to test the performance of global planning, a complex scenario is also designed, which is composed of multi-obstacles.

To model the unknown environment in MATLAB (version: 2010a), the parameter is set as below. Size of whole map is 50 cm × 50 cm, starting point coordinate is (−20, −20), target point coordinate is (20, 20), and the velocity of the robot is 1 cm/s. There is no pause during the whole traveling process. Robot should arrive at the target point at a predetermined time; if not, the experiment result will be judged as failed. Each scenario was repeated 50 times to distinguish system with CBR from system without CBR. The distance and time below represent the average path length and average time consumption from start point to target point, respectively.

One linear obstacle

In scenario 1, the linear obstacle consists of four walls including four sides and four angles. Every side or angle is a separate case; in total, there are eight cases in this scenario. Planning path with EMMAPF method, robot will update its move direction on case base constantly by comparing dist1 with dist2 when it meets the obstacle wherever on the four sides or the four angles. At the same time, system calculates the corresponding transfer angle, and finally realizes the robot navigation and obstacle avoidance.

The specific implementation process is as follows. At first, in the first corner, the robot met an angle-type obstacle. After comparing the value between dist1 and dist2, system judged that draw toward the vertical wall will be better. It can be known that $\mathrm{rightAngle}=0$ , $\mathrm{angle}=\pi /2$ (in Figure 6(b)), calculated by equation (13), we got the result that $\mathrm{resetdirection}=\pi /2$ , which means that the robot will do a vertical movement. In this case, the robot executed a circular motion around the corner instead of the previous movement toward the corner. Second, in the second corner, after finishing circular motion, robot walked along the vertical wall. At last, in the third point, the intended direction of robot ran away from the corner, so that there is no need to make the robot to flee from the influence of obstacles. In this scenario, there is eight basic cases to be included in a one linear obstacle case.

Figure 6.

Path with (a) “MAPF” method and (b) “EMMAPF” method in scenario 1.

As it can be seen from Table 1, “EMMAPF” method reduced the average time almost by 9.7%, and the distance from start point to target point was reduced almost by 6.2%.

Table 1.

Average time and distance of the path in scenario 1.

Scenario 1	Time (s)	Distance (cm)
MAPF	62.703	63.748
EMMAPF	54.578	59.616

MAPF: modified artificial potential field method; EMMAPF: experience mixing with modified artificial potential field method.

One convex polygon obstacle

In scenario 2, the convex polygon consists of four walls. Every side or angle is a separate case; in total, there are eight cases in this scenario. Planning path with EMMAPF method, robot will update its move direction on case base constantly by comparing dist1 with dist2 when it met a linear obstacle in the first corner. After comparing the value between dist1 and dist2, system judged that move toward upper left will be better. It can be known that $\mathrm{rightAngle}=5\pi /6$ (in Figure 7(b)), calculated by equation (12), we got the result that $\mathrm{resetdirection}=5\pi /6$ , which means that robot will move toward upper left. At the second corner, robot met an angle-type obstacle. Similarly, calculated by empirical formula, we got the result that robot will deflect toward upper right; deflective angle will be the global perspective of the border length that is equal to 6. On the sharp point robot invoked “driveCorner” function to make the path smoother. Then, after the end of the arc movement, robot met a linear case to navigate it to the target along the wall. In the third corner, an angle-type obstacle case was used to make it flee from the influence of obstacle and move to the target directly. In this scenario, it consists of eight basic cases, but there are four basic cases to be used by EMMAPF method to achieve the best path planning.

Figure 7.

Path with (a) “MAPF” method and (b) “EMMAPF” method in scenario 2.

As it can be seen from Table 2, “EMMAPF” method reduced the average time almost by 7.5%, and the distance from start point to target point was reduced almost by 3.0%.

Table 2.

Average time and distance of the path in scenario 2.

Scenario 2	Time (s)	Distance (cm)
MAPF	63.05	66.91
EMMAPF	58.29	64.56

MAPF: modified artificial potential field method; EMMAPF: experience mixing with modified artificial potential field method.

One concave polygon obstacle

There are many shapes of concave obstacles. In this scenario, we chose a common shape, which shows in Figure 8 to do this simulation. The concave polygon consists of eight walls including eight sides and eight angles. Besides the identical cases, there are total nine separate cases in this scenario. In this simulation, totally there are five used cases during robot’s movement including two linear cases and three angle-type cases. The path planning result of two linear walls with border length that is equal to 14 and 2 is horizontal movement to the right. For those three-angle-type cases where the lengths of left and right side are (2, 5), (2, 7), and (14, 5), the deflective angles are $7\pi /4,\pi /4,\mathrm{and}7\pi /4$ , respectively. As it can be seen from Figure 8, EMMAPF changed the path of MAPF and achieved better path navigation.

Figure 8.

Path with (a) “MAPF” method and (b) “EMMAPF” method in scenario 3.

Scenario 3 is a concave polygon obstacle environment. Using CBR method is more effective in the performance of time and distance. The data in Table 3 show that using this method reduced the traveling time by 3.3% and distance reduced by approximately 3.2%.

Table 3.

Average time and distance of the path in scenario 3.

Scenario 3	Time (s)	Distance (cm)
MAPF	59.34	62.07
EMMAPF	57.56	60.86

MAPF: modified artificial potential field method; EMMAPF: experience mixing with modified artificial potential field method.

Complex multi-obstacles

In scenario 4, we built an overall case base consists of triangle, trapezium, parallelogram, and the other basic obstacles which were introduced in Figure 10. Through case retrieval system, we test the most similar matching case. If there is any unreasonable path, correct it and re-store into the case base. In addition, fuzzy logic method ⁷ is selected to be tested in the contrast experiment. Fuzzy logic, similar to our proposed EMMAPF, is also a method to deal with path planning in unknown and dynamic environment in real time, and it could also achieve optimal local path planning.

For fuzzy logic method, the movement of the robot in the system is done by a fuzzy inference system (FIS) planner. The FIS takes four inputs. There are angle to goal (α), distance from goal (d_g), distance from obstacle (d₀), and turn to avoid obstacle (t₀). There is a single output that measures the angle (β) that the robot should turn along the direction. The rules can be classified into two major categories. The first category of rules tries to drive the robot toward the goal. The second category of rules tries to save the robot from obstacles. If an obstacle is very near, the second category of rules becomes very dominant. A total of 11 rules are identified; these are given in Figure 9. The numbers in parentheses denote the weights.

Figure 9.

FIS rules.

The comparison of path performance is shown in Figure 10 and Table 4.

Figure 10.

Path with (a) “MAPF,” (b) “EMMAPF,” and (c) “Fuzzy logic” method in scenario 4.

Table 4.

Average time and distance of the path in scenario 4.

Scenario 4	Time (s)	Distance (cm)
MAPF	100.415	78.458
EMMAPF	88.260	72.312
Fuzzy logic	71.307 (uncompleted)	58.833 (uncompleted)

MAPF: modified artificial potential field method; EMMAPF: experience mixing with modified artificial potential field method.

In Figure 10, it is obvious that robot gets trapped in the local minimum problem and cannot reach the target point using fuzzy logic method, while MAPF and EMMAPF method can complete robot autonomous navigation effectively. The robot will unable to complete effective path navigation when it meets new and unknown environment, because the rules of fuzzy logic are preset. However, the actual situation is that not all the rules can be considered in advance. In this article, as described in the previous section, the local minima problem can be solved using MAPF method. Moreover, it can also be solved by our proposed EMMAPF which is an optimal method to combine MAPF with CBR mechanism. In CBR, the cases of complex obstacles can be retrieved by two basic build-in case models which is composed of “linear-type obstacle model” and “angle-type obstacle model.” In the process of the global obstacle avoidance, system will invoke CBR algorithm using its past experience to achieve obstacle avoidance when obstacles are recognized as known type; otherwise, it will invoke the “MAPF” method to solve the current problem, and the new case will be self-retained into the case base if the obstacle type is considered as an unknown. In addition, as can be seen from the data in Table 4, by comparing our proposed EMMAPF method with MAPF method, the runtime is reduced by approximately 12.1%, and the distance is reduced by 7.8%; although the time-consuming performance of fuzzy logic method is good and the path distance of local path is optimal in some cases, there exists some abnormal problems such as the path is not optimal and the target is unable to be reached when the rules of fuzzy logic are incomplete.

Simulation result analysis

Based on the experimental results, we can conclude that the path of “EMMAPF” method is more optimal than “MAPF” method and “fuzzy logic” algorithm. The path generated through “MAPF” method is safe but long and passes through many unnecessary places. Using “EMMAPF” method to obtain the available prior experience can help the robot to make the best decisions when it encounters the obstacles.

Real test

In order to control the real-time movement of the robot to verify the effectiveness of this method, we take an actual test based on a Kinect sensor with the mobile robot.

Kinect is a motion sensing input device that is used by Microsoft Xbox 360video game console and WindowsPCs. Besides the main business as a gaming device, it is also treated as a good sensor to identify the category of obstacles for robot. In brief, Kinect includes a color (RGB) camera, an infrared depth sensor, an accelerometer, four microphones, and a motor to adjust the tilt. Its detection depth is up to 5 m.

Color camera obtains an actual image of the current environment. Infrared depth sensor collects the depth data, which indicates the distance between the objects and the camera. Regardless of the light condition around the environment, Kinect could capture 640 × 480 registered image and depth points at 30 frames/s. After analyzing the related environmental information, we could obtain the features of the obstacles. Figure 11 shows the process of the experiment. We implement our experiments based on the robot operating system (ROS) platform.

Figure 11.

The process of the experiment.

In fact, model environment depends on the sensor data type and the purpose of using generated map. Figure 12 shows how to build a model of the environment. ²¹

Figure 12.

Building a model of the environment.

Mapping into two-dimensional space

In the beginning, Kinect scans the environment to generate RGB-D images. Successive frames of RGB-D information are captured during the movements of the robot at 30 frames/s, and then obtain the point clouds from the depth image. A point cloud is always defined as a set of irregular, unorganized points in three dimensions (3D). point cloud data (PCD) files contain the message including each point coordinate (x, y, and z) and the color information. Figure 13 illustrates an example of generating point cloud in our real-world test scene.

Figure 13.

An example of generating point cloud. (a) RGB image (left) and depth information (right) taken by a RGB-D camera and (b) point cloud.

Because of the point cloud data are based on Kinect-centered coordinate, so we need to transform the points into world coordinates when we map the point cloud into a two-dimensional (2D) continuous space. Two steps have been taken. First, keep the points between the min and max height which Kinect could detect by equation (27). Second, map those point clouds into equivalent 2D continuous space by equation (28). $(X,Y)$ is the corresponding coordinate that (x, y, and z) is mapped on

$$P=\{(x,y,z)|h_{min}<y<h_{max}\}$$

(27)

$$\begin{array}{cc}\multicolumn{1}{c}{(X,Y)=}& (u-(z*\sin \theta +x*\cos \theta ),\hfill \\ \multicolumn{1}{c}{}& v+(z*\cos \theta -x*\sin \theta ))\hfill \end{array}$$

(28)

where $(u,v)$ represents the coordinate of the Kinect and $\theta$ means the global angle of the Kinect.

Figure 14 shows the effect of mapping point cloud in Figure 13 (b) into 2D space.

Figure 14.

Map point cloud into 2D space.

The more the frames are captured, the more points are included in the 2D-mapped space. The 2D-mapped points with new frames would be added into the world coordinate with the increase in time.

Data clustering

The next step is to cluster the points of 2D map; some kinds of clustering algorithm have been tried to apply in data clustering; in this research, density-based spatial clustering of applications with noise (DBSCAN) is the best approach which is capable of finding arbitrarily shaped clusters. It is very flexible with unusual shape of dense point areas. Figure 15 illustrates the resulting clusters which could represent one shape in the space.

Figure 15.

Data clustering by DBSCAN algorithm.

Concave-hull approach

P Wasmeier ²² implemented a function in MATLAB called hullfit, which could calculate a concave-hull of a data set. Two parts are included in this algorithm.

First, apply the concave-hull to obtain vertices of corresponding convex-hull and classify them as clockwise. Next, calculate the distances among each two neighbors’ vertices to find any distance greater than maximum allowed distance. If any points returned, use some conditions to find another proper point in the data set as the next vertex.

More detailed description is introduced in Mojtahedzadeh. ²³ Here, we apply the function hullfit to represent obstacles with the best polygons to fit. Figure 16 shows one final model of the environment during the robot moving to the target.

Figure 16.

The final model of the environment.

Thus, we could get the category of the obstacle’s front shape by the Kinect sensor, such as line or concave polygon, which is the useful information of the obstacles used to complete the path planning. We imitate scenario 4 to verify the efficiency of “EMMAPF” algorithm in real world. The size of the area is 5 m × 5 m. Kinect is placed in the front of the omni-wheel robot.

The black dot in the top right corner of the scene is the target. We set the origin velocity of the robot at 0.1 m/s. Figure 17 shows the actual process of robot navigation in a complex multi-obstacle environment. The information of the obstacles is unknown in advance.

Figure 17.

Process of the robot using “EMMAPF” method in a complex multi-obstacle environment.

Table 5 illustrates the statistical data of experiments in simulation and actual test. Time used in actual test is a little more than in simulation, while distance is shorter. This deviation is caused by the fiction that exists between the wheels of robot and the floor.

Table 5.

Comparison between simulation and actual test.

	Scene area	No. of obstacles	Running time	Distance
Simulation	0.5 m × 0.5 m	6	88.26 s	0.723 m
Actual test	5 m × 5 m		90.13 s	7.024 m
Ratio	1:10	1:1	1:1.02	1:11.2

As it can be seen from Figure 18, two paths are shown in different colors. Blue line represents the path in simulation environment, while the red line represents the actual path in real-time physical test environment. Except for the robot traveling around the corner, the deviation of the path is small. Figure 19 records that the path deviation exists on each moment in the movement. In fact, the deviation is small (<0.1 m) and is acceptable. So, we can conclude that the “EMMAPF” algorithm could be applied in the real world successfully.

Figure 18.

A planned path by simulation (blue line) and an actually followed path (red line) using “EMMAPF” method.

Figure 19.

Deviation between the planned path and the actually followed path.

Conclusion and future work

In this article, a new approach EMMAPF which combines case-base reasoning method with the modified APF method is put forth to get an optimal path and better algorithm efficiency. In CBR, we innovatively consider that all the complex obstacles are retrieved by two kinds of basic build-in obstacle models (linear obstacle and angle-type obstacle). In the process of the global obstacle avoidance, system will invoke CBR algorithm using its past experience to achieve obstacle avoidance when obstacles are recognized as known type; otherwise, it will invoke the “MAPF” method to solve the current problem, and the new case will be retained into the case base if the obstacle type is considered as an unknown. In simulations, three different obstacle cases which retrieved by the proposed two basic build-in case models have been designed to run the experiments, respectively, including one linear obstacle, one concave polygon obstacle, and one convex polygon obstacle. In order to test the performance of global planning, a complex scenario is also designed, which is composed of multi-obstacles. We illustrated the obstacle avoidance process and effect of those four obstacle cases using our proposed EMMAPF compared with MAPF and fuzzy logic algorithm. In actual test, by acquiring the RGB-D images from the Kinect sensor and building the model of the final environment, robot could obtain the useful information of the obstacles and utilize the “EMMAPF” method to deal with path planning in unknown and dynamic environment in real time. According to simulation and actual test, we can come to the conclusion that this method has been proved applicable to the dynamic real-time obstacle avoidance under unknown and unstructured environment, and it greatly improved the performance of robot path planning that not only reduced the time consumption but also shorten the moving distance.

In future, there are two major issues that we need to pay more attention. One is to improve the performance of CBR in real time, some measures need be taken to shorten the time in searching and matching; otherwise, time delay in CBR mechanism would lead to the failure of the obstacle avoidance. The other issue is to improve the accuracy of building a model of the environment. More different methods should be studied and compared in data clustering. The detection of the obstacles in the environment has a significant effect on the results of the “EMMAPF” method. With the development of this method, our system will become a true real-time system to deal with path planning for mobile robot in the future.