Planning Expected-time Optimal Paths for Target Search by
Robot
∗
Botao
Zhang
Intelligent Mobile Robotics Laboratory
Hangzhou Dianzi University
Hangzhou, Zhejiang, 310018, China
h.hafoc@gmail.com
Shirong
Liu
Intelligent Mobile Robotics Laboratory
Hangzhou Dianzi University
Hangzhou, Zhejiang, 310018, China
liushirong@hdu.edu.cn
Abstract— In this paper, a path planning approach for finding
an optimal path is proposed to reduce the expected-time in
target search by robot. This approach employs a heuristic
algorithm to generate a basic path and minimize the expected-
time. Considering different direction may lead to different
expected-time in a same loop, a direction choosing method
is presented to improve the performance of this heuristic
algorithm. Then, based on the improved algorithm, a two-level
path planning approach is investigated. At the top level, the
improved heuristic algorithm is used to generate a sequence
of observation points. At the lower level, the Artificial Potential
Field (APF) is employed to plan paths among observation points.
Simulations and experiments demonstrated that this approach
can reduce the expected time for target search.
Index Terms— Mobile robot, Target Search, Optimal
Expected-time, Path Planning.
I. I NTRODUCTION
Target search refers to using one or more robots to search
for one or more targets, which involves machine vision,
map building, path planning and so on[1], [2], [3]. Path
planning for target search is one of the most challenging
problems in robotics, and has attracted much attention over
the past decades in applications and in theory. Many planning
approaches have been presented to deal with the target search
problem for various applications, such as plant exploration
[4], autonomous search and rescue [5] and chemical industry
[6].
In terms of path planning, previous target search ap-
proaches can be classified into two classes: continuous
planning and discrete planning. For continuous planning
approaches, robots are supposed to scan continuously as they
move. These approaches are identical to human behavior, but
it is very difficult to get the globally optimal solution [7]. As
for discrete planning approaches, in the path planning stage,
robots are supposed to visit some particular locations in a
certain order. Then, robots scan the environment discretely
or continuously with the generated sequence[2]. The discrete
∗
This work is partially supported by the National Natural Science
Foundation of China (Grant No. 61175093).
planning approach has become popular for its feasibility and
validity in applications.
In discrete planning approaches, there are several criteria
to evaluate the performance of exploration strategies, such as
the distance, the time and the number of locations [3], [8].
This study focuses on the expected-time. In previous studies,
some researchers believed that plan a path with the optimal
time is equated to plan a path with the shortest distance. This
theory is based on a hypothesis that the velocity of the robot
is a constant. According to this hypothesis, it is necessary
to optimize the distance robot traveled, if you want to find
the goal as quick as possible. And then, some researchers
discovered that minimize time is different from minimize
the distance, for example, a trajectory for target search that
minimize the expected-time has been proved not necessarily
minimize the distance [2]. Therefore, they believed that the
time instead of just the distance must be considered. Based
on this theory, the expected-time was introduced in to path
planning for the target search. In the study on expected-time
path planning, we found that different direction in loops leads
to different expected-time, no studies so far has been made
to this problem.
This study aims to find an approach to solve the problem
that different direction leads to different expected-time in
loops, and then employs it to improve the performance of a
heuristic exploration strategy. And then, the proposed strategy
is applied to search probabilistic environments, in which the
robot scans the environment discretely at several observation
points and these observation points are given as inputs. The
above experiments simplify the target search problem, which
is beneficial to consider difficult optimization problem. An
improved artificial potential field is used to generate Locally
paths [9].
This paper is organized as follows. Section 2 discusses the
target search problem and presents the problem of different
direction leads to different expected-time in loops. In section
3, an improved heuristic exploration strategy is proposed and
compared with the original one. Some experiment results are
presented in section 4, and a conclusion is provided in the
last section.
3URFHHGLQJVRIWKHWK
:RUOG&RQJUHVVRQ,QWHOOLJHQW&RQWURODQG$XWRPDWLRQ
-XO\%HLMLQJ&KLQD
3881
978-1-4673-1398-8/12/$31.00 ©2012 IEEE