A path planning strategy for searching the most reliable path in uncertain environments

Abstract

A path planning method for searching the most reliable path in uncertain environments is proposed in this article. When a robot chases a target in a semi-structured workspace with hazards and uncertainty, which path it takes is of great matter as different paths can lead to diverse risks. To “enlighten” the robot on a wiser choice, a reliability-based topological map is built, in which it is possible to add uncertainty information such as threats and road condition to topological nodes. With this map, the robot is possible to minimize risks in carrying out a target search task. Further simulation and physical-world experiments indicate that the most reliable path method generates a path a bit longer, following which the robot encounters less risks.

Keywords

Robotics probabilistic robotics target search path planning

Introduction

Target search refers to search for one or several targets in an environment with one or more robots, which involves image processing and computer vision,^1
–3 path planning,^4,5 simultaneous localization and mapping, and so on.^6,7 During the past decade, path planning for target search is one of the most interesting and challenging problems. Different planning methods have been proposed to deal with target search problems for various applications, such as home service, plant and deep sea exploration, autonomous rescue and security patrol.^8,9

The existing methods can be roughly classified into two kinds: deterministic target search methods and probabilistic target search methods. In the earlier stage, studies of path planning for target search mainly focused on deterministic approaches, in which uncertainties in the environments are ignored. In these works, time is the most important index to evaluate exploration strategies. However, most workplaces, such as a private home and an earthquake-stricken area, are unpredictable and uncontrollable. In addition, when the mobile robot lacks critical information for its tasks,^10,11 which may include limited sensors, algorithmic approximations, and so on, uncertainty also appears.^12,13 As a result, the robot has to cope with increasing uncertainties in carrying out its tasks.¹⁴ Therefore, researchers introduce probabilistic target search approaches, which are more robust in dealing with uncertainties. Sarmiento et al. verified that a route that optimizes the expected time does not necessarily optimize the route length in some target search tasks⁴ and presented a continuous search method to optimize the expected time for target search. Sebastian believed that the path of a robot could be threatened by bad conditions of the workspace, which increased uncertainty.¹⁵ Zhu et al. pointed out that the terrain could influence some robot tasks for the robot localization and the traversability of path.¹⁶

This article aims to present a planning approach for the most reliable path in uncertain environments and then applies it to improve the reliability in robot target search tasks. A reliability-based topological map is built, in which it is possible to add uncertainty information such as threats and road condition to topological nodes. With the topological map, the path planning method is employed to generate a reliable path for the robot’s target search. Compared with Zhang et al.’ study,¹⁷ in this article, more theoretical analysis and detailed experiment tests are provided: For example, global objective function for the most reliable path planning is discussed, method of how to plan the path between landmarks is elaborated, and target tracking systems for target search is presented.

The organization of this article is as follows. In the section “Problem definitions,” the reliability-based topological map and the target search problems are discussed. In the section “A strategy for finding the most reliable path,” a path planning strategy for finding the most reliable path is proposed. Experimental results are provided and discussed in the section “Experimental results.”

Problem definitions

Reliability-based topological map

With the absence of uncertainty, a robot can maintain a constant speed; thus, time is the most important criterion to evaluate the quality of exploration strategy. In this case, the shorter road is superior to any longer ones. However, in physical world, narrow corridors, uneven terrain, or turnings could slow and even bring damage to a robot.

Figure 1 shows two simple environments, through which different threats and uncertainties that a mobile robot may face will be illustrated. It is drawn by map editor of three-dimensional operating system (3DO) company. In Figure 1(a), path B is shorter than path A, but it is close to a river; a robot is at risk of falling into water when running along the path. Therefore, path A is more reliable than path B. In Figure 1(b), path B is shorter, but its surface configuration is terrible, a robot might be trapped. In cases like these, the most reliable road may not be the shortest one. Thus, uncertain factors alike should be considered in path planning for a mobile robot.

Figure 1.

Reliability-based topological map.

For a topological map $G (J, O)$ , which is composed of a vertex set $O = {O_{k} | O_{k} \in G, k = 1, 2,$ $3, ..., m}$ and an edge set $J = {J_{k} | J_{k} \in G, k = 1, 2, 3, ..., n}$ , reliable probability $p_{O_{i} O_{j}}$ is a value to estimate the reliability between O_i and O_j. If there are x factors having influence on reliable probability $p_{O_{i} O_{j}}$ , subreliable probabilities of these factors can be represented as $p_{O_{i} O_{j}}^{1}, p_{O_{i} O_{j}}^{2},$ $p_{O_{i} O_{j}}^{3}, \dots, p_{O_{i} O_{j}}^{x}$ . $p_{O_{i} O_{i}}$ is calculated by

p_{O_{i} O_{j}} = f (p_{O_{i} O_{j}}^{1}, p_{O_{i} O_{j}}^{2}, p_{O_{i} O_{j}}^{3}, \dots, p_{O_{i} O_{j}}^{x}) = p_{O_{i} O_{j}}^{1} p_{O_{i} O_{j}}^{2} p_{O_{i} O_{j}}^{3} \dots p_{O_{i} O_{j}}^{x}

Figure 2 is a toy-like reliability-based topological map $G_{1} (J, O)$ , the reliable matrix with this simple environment $G_{1} (J, O)$ is

Figure 2.

Simple environments.

{\hat{D}}_{1} = [\begin{matrix} {\hat{p}}_{11} & {\hat{p}}_{13} & {\hat{p}}_{14} & {\hat{p}}_{15} \\ {\hat{p}}_{21} & {\hat{p}}_{22} & {\hat{p}}_{23} & {\hat{p}}_{24} \\ {\hat{p}}_{31} & a_{32} & {\hat{p}}_{33} & {\hat{p}}_{34} \\ {\hat{p}}_{41} & {\hat{p}}_{42} & {\hat{p}}_{43} & {\hat{p}}_{44} \end{matrix}]

where

{\hat{p}}_{i j} = {\begin{matrix} - \ln (p_{O_{i} O_{i}}) & p_{O_{i} O_{i}} \in (0, 1) \\ \inf & p_{O_{i} O_{i}} = 0 \\ 0 & p_{O_{i} O_{i}} = 1 \end{matrix}

Target search problem

For a semi-structured environment E with some real-time changes, for example, a building where several people walk about, a set of observation points $O = {O_{k} | O_{k} \in E, k = 1, 2, 3, \dots, n}$ at which robot can sense the environment is given as input. The location of the target is stochastic and updates at an interval. Once the sensor network captures the target and sends its location, the robot should plan the most reliable path l to the target.

Therefore, planning the most reliable path for target search becomes a global maximization optimization problem, and the global objective function is

f (C) = \max (\prod_{i = 1}^{n - 1} p_{O_{i} O_{j}})

where $C = {O_{1}, O_{2}, O_{3}, O_{4}, \dots, O_{n}}$ denotes a sequence of observation points, $p_{O_{i} O_{j}}$ is a value to estimate the reliability between O_i and O_j.

A strategy for finding the most reliable path

Sequence planning

The Floyd–Warshall algorithm is a well-known and well-studied algorithm to search for the sequence of vertexes and edges with minimum weight in directed and undirected graph.¹⁸ In this study, Floyd–Warshall algorithm will be improved to solve the most reliable path problem, as there are some disparities between the two.

For computer graphics, the Floyd–Warshall algorithm is used to find the shortest path in a weighted graph; it has little to do with real feasibility of robot tasks in the physical world. Therefore, in target search problem, if the arranged path is blocked or destroyed, the robot needs to plan another one to achieve its objective immediately.

In the Floyd–Warshall algorithm, any weight of edge is constant, while the reliable information of environments should be updated on time in the latter task.

There are many factors influencing the reliability of roads in target search, varying from robot to robot, task to task. Therefore an appropriate $p_{O_{i} O_{j}}^{x}$ should be adopted and equation (1) is used to calculate the reliable probability of road. The initial reliable probability is manually set on the basis of human experiences. The probability matrix D₁ is used to describe the reliable probability of a whole map. According to equation (1), the probability matrix D₁ is given by

D_{1} = [\begin{matrix} p_{O_{1} O_{1}} & p_{O_{1} O_{2}} & \dots & p_{O_{1} O_{n}} \\ p_{O_{2} O_{1}} & p_{O_{2} O_{2}} & \dots & p_{O_{2} O_{n}} \\ ⋮ & ⋮ & ⋮ \\ p_{O_{n} O_{1}} & p_{O_{n} O_{2}} & \dots & p_{O_{n} O_{n}} \end{matrix}]

where there are n vertexes in this topological map. By equation (3), the probability matrix D₁ can be transformed into the reliable matrix ${\hat{D}}_{1}$ for adopting the Floyd–Warshall

{\hat{D}}_{1} = [\begin{matrix} {\hat{p}}_{11} & {\hat{p}}_{12} & \dots & {\hat{p}}_{1 n} \\ {\hat{p}}_{21} & {\hat{p}}_{22} & \dots & {\hat{p}}_{2 n} \\ ⋮ & ⋮ & ⋮ \\ {\hat{p}}_{n 1} & {\hat{p}}_{n 2} & \dots & {\hat{p}}_{n n} \end{matrix}]

The sequence planning algorithm is as follows.

Step 1. Compute the probability matrix D₁ according to the workspace with equations (1) and (5);

Step 2. Compute the reliable matrix ${\hat{D}}_{1}$ using equations (3) and (6);

Step 3. Sequence planning with the Floyd–Warshall algorithm.

Step 4. If the update time is up or the robot is on a dead road, update the reliable information and location of target, and repeat step 1.

Algorithm Se_Planning( )

initialize $p_{O_{i} O_{j}}^{1}, p_{O_{i} O_{j}}^{2},$ $p_{O_{i} O_{j}}^{3}, \dots, p_{O_{i} O_{j}}^{x}$

while(the task is still in progress)

calculate $p_{O_{i} O_{i}}$ by equation (1)

calculate ${\hat{D}}_{1}$ with equation (2)

for(k = 1; k<=n; k++)

for(i = 1; i<=n; i++)

for(j = 1; j<=n; j++)

if (the path with max reliability through the node O_m)

then $O_{i, j, m} \Leftarrow O_{i, m, m - 1} + O_{m, j, m - 1}$

end if

if (the update time is up or the robot is on a dead road)

update $p_{O_{i} O_{j}}^{1}, p_{O_{i} O_{j}}^{2},$ $p_{O_{i} O_{j}}^{3}, \dots, p_{O_{i} O_{j}}^{x}$

Through the above sequence planning algorithm, the most reliable path can be obtained. Theoretical evidences of the optimality can be found in literature.¹⁹ Floyd–Warshall algorithm is often used to find the minimum weight path in graph theory.²⁰ The most reliable path problem is a kind of weight optimization problem in a connected graph. Therefore, the Floyd–Warshall algorithm can find the global maxima.¹⁹

APF trajectory planning

With the Floyd–Warshall algorithm, we can get a sequence of vertexes $O_{4}, O_{1}, O_{3}, O_{7}, ..., O_{k}$ , but we still need to find the feasible road without obstacles between O₄ and O₁, O₁ and O₃, … …. Thus, an improved artificial potential field (APF) is applied to avoid surrounding obstacles and generate a path between any two adjacent vertexes, such as: O₄ and O₁, O₁ and O₃, … …. In recent decades, many APF approaches and their improved versions were proposed, and a lot of potential functions were developed to describe obstacles.^21,22 It is difficult to employ these existing functions to describe irregular obstacles. A new general method is used here to deal with this problem in environments surrounding irregular obstacles. To match the potential functions with obstacles, it is assumed that point charges uniformly distribute along boundaries of irregular obstacles, as shown in Figure 3.

Figure 3.

Point charges in the improved artificial potential field.

The combined field is

T (q_{r}, q_{i}, q_{g}) = \sum_{i = 1}^{k} T_{rep} (q_{r}, q_{i}) + T_{att} (q_{r}, q_{g})

in which, the attractive function is $T_{att} (q_{r}, q_{g})$ and the repulsive function is $T_{rep} (q_{r}, q_{i})$ , q_g denotes the location of target, q_r is the location of a mobile robot, and q_i denotes the location of a charge.

According to the attractive function and repulsive function in Ge and Sui’ study,²³ an improved attractive function is

T_{att} (q_{g}, q_{r}) = {\begin{matrix} α ρ^{2} (q_{g}, q_{r}) + ξ ρ (q_{g}, q_{r}), & ρ < ρ_{λ} \\ α ρ^{2} (q_{g}, q_{r}), & ρ \geq ρ_{λ} \end{matrix}

The repulsive function is

T_{rep} (q_{r}, q_{i}) = {\begin{matrix} \frac{σ}{2} {(\frac{ρ_{0} - ρ (q_{i}, q_{r}) + ∊}{(ρ (q_{i}, q_{r}) - ∊) ρ_{0}})}^{2}, & ρ (q_{i}, q_{r}) \leq ρ_{0} \\ 0, & ρ (q_{i}, q_{r}) > ρ_{0} \end{matrix}

In which $ρ_{λ} = τ R_{robot}$ , R_robot is the size of the robot; ρ₀ is the influence scope of obstacles; ε is a small positive constant; α, σ, τ, and ξ are positive constants; the distance between q_r and q_g is $ρ (q_{g}, q_{r})$ ; and the distance between the mobile robot and q_i is $ρ (q_{i}, q_{r})$ .

The procedure figure of the strategy for finding the most reliable path in environments with uncertainty is shown in Figure 4.

Figure 4.

Procedure figure of the most reliable path planning.

Experimental results

In this section, simulation results and cases studies in a physical world are detailed. A robot named Powerbot is applied to search for an orange ball in synthetic environments.

Simulations

In simulations, the robot moves at a speed of 0.5 m/s, S₀ denotes the initial location of the mobile robot.

In environment I, the narrow corridor is a threat factor for the robot. $p_{O_{i} O_{i}}$ can be calculated according to the width and length of corridors.

p_{O_{i} O_{j}} = {\begin{matrix} 0 & W_{cor} \leq R_{dia} \\ \frac{W_{cor}}{γ} & R_{dia} < W_{cor} < 3 R_{dia} \\ 1 & W_{cor} \geq 3 R_{dia} \end{matrix}

where

γ = 3 R_{dia} \sqrt[3]{ceil (\frac{L_{cor}}{R_{dia}})}

W_cor and L_cor denote the width and the length of a narrow corridor; R_dia is the diameter of the robot; and ceil (A) is the nearest integer greater than or equal to A.

The shortest path is generated by the Dijkstra and APF, as shown in Figure 5. The most reliable path planned by the proposed algorithm is shown in Figure 6. From the results in Table 1, we can see that the most reliable path is not the shortest path. By this way, the robot might spend more time accomplishing the task; however, it takes less risks. This toy-like environment is only used to show how the proposed method works when it faces risks.

Figure 5.

The path generated by the Dijkstra and APF in environment I. APF: artificial potential field.

Figure 6.

The path generated by the proposed method in environment I.

Table 1.

Comparison between the shortest and the most reliable path in environment I.

	The shortest path	The most reliable path
Reliability	17.2%	43.0%
Time (s)	21.99	32.84
Average velocity (m/s)	0.50	0.50

Environment II is used to simulate an indoor environment, in which there are 10 observation points. Each edge between two points has different reliability. A mobile dangerous hunter, which can cause damage to the robot, is put into the workspace.

The shortest path is generated by the Dijkstra and APF, as shown in Figure 7. Table 2 shows that time used to complete the target search task with the Dijkstra and APF algorithm is shorter than that of the most reliable path approach in this particular environment. In most cases, the robot would choose the path in Figure 8; however, if it encounters the hunter, the route will be replanned, as shown in Figure 9. In the above situation, the performance of the improved APF is shown in Figure 10.

Figure 7.

The Dijkstra and APF in environment II. APF: artificial potential field.

Table 2.

Comparison of the shortest and the most reliable path in environment II.

	The shortest path	The most reliable path	The most reliable path (encounter danger)
Reliability	11.7%	79.3%	62.4%
Time (s)	75.5	103.0	189.6
Average velocity (m/s)	0.50	0.50	0.5

Figure 8.

The most reliable path in environment II.

Figure 9.

The most reliable path in environment II (encounter danger).

Figure 10.

The improved APF in environment II (encounter danger). APF: artificial potential field.

Physical-world experiment

The environment for applications is built in the laboratory. In this physical world, the mobile robot cannot keep a constant speed for a lot of reasons, such as the friction of ground, turnings at corners. The robot also needs time to detect obstacles and the target. In the following experiments, a robot named Powerbot was applied to look for a table tennis ball. The Powerbot is a differential drive robot equipped with vision systems, segmented bump, ranging sonar and laser.

A CamShift algorithm with Kalman filter^24,25 is used to recognize the target, track the table tennis ball with histogram, as shown in Figure 11. The searching window can adjust adaptively according to the size of targets. The robot could track the moving balls and partially obscured target with this algorithm.

Figure 11.

Target search system.

Five independent runs of each method is used to test the average of time cost and reliability, as shown in Table 3 and Figure 12. Compared with the shorter path, the most reliable path method generates a road a bit longer, and the robot takes more time to finish the task. When the robot travels along the shortest path, the average velocity is lower, because it spends too much time in preventing itself from colliding obstacles. Feature map in Figure 13 is built by the robot using laser sensors. According to the trajectory of robot in Figure 13, the most reliable path planning method chose a path with less narrow corridors in this particular environment.

Table 3.

Comparison of the shortest and the most reliable path.

	The shortest path	The most reliable path
Reliability	30.4%	65.5%
Time (s)	31	37

Figure 12.

The experimental environment for the most reliable path planning.

Figure 13.

The most reliable path.

Conclusions

A strategy for finding the most reliable path in environments with uncertainty has been proposed in this study. It is a very conservative method, especially suitable for situations in which it is difficult to bear any damage to a robot. In addition, this approach is a good choice for carrying out the task if the time is abundant. Simulation results and physical-world experiments have proved that with the proposed method, the robot performs well on finding the most reliable path. Whereas this does not mean that the proposed method is a panacea, it is not suitable for the situation that the time is pressing.

Footnotes

Author’s Note

Authors Botao Zhang and Yong Liu should be considered co-first authors.

Acknowledgment

This article is a revised and expanded version of a paper entitled A Strategy for Finding the Most Reliable Path in Uncertain Environments presented at The 2015 International Conference on Climbing and Walking Robots, Hangzhou, September 6–9, 2015.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the Natural Science Foundation of Zhejiang Province (no. LQ14F030012), the National Natural Science Foundation of China (no. 61503108 and 61375104), the Zhejiang Open Foundation of the Most Important Subjects, and the National Natural Science Foundation Project of China (U1509210).

References

Cao

Cheng

Zhou

. Spiking neural network based target tracking control for autonomous mobile robots. Neural Comput Appl 2015; 26(8): 1839–1847. DOI: 10.1007/s00521-015-1848-5.

Hausman

Müller

Hariharan

. Cooperative multi-robot control for target tracking with onboard sensing. Int J Robot Res 2015; 34(13): 1660–1677. DOI: 10.1177/0278364915602321.

Aydemir

Pronobis

Gobelbecker

. Active visual object search in unknown environments using uncertain semantics. IEEE Trans Robot 2013; 29(4): 986–1002. DOI: 10.1109/TRO.2013.2256686.

Sarmiento

Murrieta-Cid

Hutchinson

. An efficient motion strategy to compute expected-time locally optimal continuous search paths in known environments. J Adv Robot 2009; 23(12–13): 1533–1560. DOI: 10.1163/016918609X12496339799170.

Lin

Wei

Yang

. Planning on searching occluded target object with a mobile robot manipulator. In: The IEEE International Conference on Robotics and Automation (ed Okamura

), Seattle, USA, 26–30 5 2015, pp. 3110–3115. Piscataway: IEEE. DOI: 10.1109/ICRA.2015.7139626.

Jiang

YX,

Liu

. Performance evaluation of feature detection and matching in stereo visual odometry. Neurocomputing 2013; 120: 380–390 DOI: 10.1016/j.neucom.2012.06.055.

Grosch

Thomas

. Geometric path Planning without maneuvers for non-holonomic parallel orienting robots. IEEE J Mag 2016; 1(2): 1066–1072. DOI: 10.1109/LRA.2016.2529688.

Anderson

Tunstel

EW,

Wilson

. Robot system to search for signs of life on mars. IEEE Trans Aerosp Electron Syst 2007; 22(12): 23–30. DOI: 10.1109/MAES.2007.4408598.

Shinji

Mineo

Takashi

. Emergency response by robots to Fukushima-Daiichi accident: summary and lessons learned. Ind Robot 2012; 39(5): 428–435. DOI: 10.1108/01439911211249715.

10.

Burgard

. Probabilistic approaches to robot navigation. IEEE Robot Automat Mag 2008; 15(2): 8–13. DOI: 10.1109/MRA.2008.925681.

11.

Liu

SE,

Hedrick

. Model predictive control-based probabilistic search method for autonomous ground robot in a dynamic environment. In: The ASME 2015 Dynamic Systems and Control Conference (ed Rizzoni

), Columbus, USA, 28–30 October 2015, pp. V003T49A003–V003T49A003. New York: ASME. DOI:10.1115/DSCC2015-9814.

12.

Geraerts

Overmars

. A comparative study of probabilistic roadmap planners. Springer Tracts Adv Robot 2004; 7: 43–57. DOI: 10.1.1.153.7628.

13.

Merhy

Payeur

. Application of segmented 2-D probabilistic occupancy maps for robot sensing and navigation. IEEE Trans Instrum Meas 2008; 57(12): 2827–2837. DOI: 10.1109/TIM.2008.926048.

14.

Brunskill

Roy

. Efficient planning under uncertainty with macro-actions. J Artif Intell Res 2011; 40: 523–570. DOI: 10.1613/jair.3171.

15.

Sebastian

. Probabilistic robotics. Communications of the ACM - robots: intelligence, versatility, adaptivity. 2002; 45(3): 52–57. DOI: 10.1145/504729.504754.

16.

Zhu

Qiu

Minor

. Terrain inclination based three-dimensional localization for mobile robot in outdoor environments. J Field Robot 2014; 31(3): 477–492. DOI: 10.1002/rob.21515.

17.

Zhang

Wang

. A strategy for finding the most reliable path in uncertain environments. In: The 2015 International Conference on Climbing and Walking Robots, Hangzhou, 6–9 September 2015. Singapore: World Scientific, 2015. p.677–684. DOI: 10.1142/9789814725248_0081.

18.

Hougardy

. The floyd-warshall algorithm on graphs with negative cycles. Inform Process Lett 2010; 110(8–9): 279–281. DOI: 10.1016/j.ipl.2010.02.001.

19.

Sanjoy

Christos

Umesh

Algorithms. McGraw-Hill Science Press, 2006.

20.

Eiselt

Sandblom

CL.

Integer programming and network models. Springer Press, 2000. DOI: 10.1007/978-3-662-04197-0_15.

21.

Hossein

Tabrizi

MHN

Alborz

. Path planning for mobile robots using iterative artificial potential field method. Cybernet Informat Technol 2011; 8(4): 28–32.

22.

Chen

XB,

. An improved path planning method based on artificial potential field for a mobile robot. Cybernet Inform Technol 2015; 15(2): 181–191. DOI: 10.1515/cait-2015-0037.

23.

Cui

. New potential functions for mobile robot path planning. IEEE Trans Robot Automat 2000; 16(5): 615–620. DOI: 10.1109/70.880813.

24.

Sun

Liu

. Combined algorithm with modified Camshift and Kalman filter for multi-object tracking. Informat Control. 2009; 38(1): 9–14.

25.

Ould-Dris

Ganoun

Canals

. Improved object tracking with camshift algorithm. In: The IEEE International Conference on Acoustics, Speech, and Signal Processing; 14–19, May ; Toulouse. Piscataway: IEEE; 2006. p. 657–660. DOI: 10.1109/ICASSP.2006.16 60428.