Environment exploration and map building of mobile robot in unknown environment 243
2 Analyse and calculate the environment information
acquired. If there is candidate, goes to step 3;
otherwise, goes to step 4.
3 Select the optimal candidate from all the candidates,
and marked this candidate as known one, goes to step 1.
4 Robot checks whether there exist candidates, if so, goes
to step 3; otherwise, goes to step 5.
5 Robot checks whether all the candidates have been
marked as explored. If there still exist un-explored
candidates, the robot moves to these candidates and the
flow goes to step 1; otherwise, the exploration
procedure ends.
The two important steps in this flowchart are candidate’s
producing and evaluating, and we will explain these two
steps in detail.
Figure 1 Environment exploration flowchart
3 Producing and evaluating of candidates
3.1 Candidate producing
Candidate producing in this paper refers the Frontier
exploration, but this method easily loses the environment
information and is difficult to cover the whole environment,
so the environment map generated is not integrated.
Besides, candidates are generally located on the frontier
area and the robot has to travel a long distance. Combining
with the concrete environment, this paper chooses the
candidate which can maximise the information gain and
also satisfy the requirements of environment exploration.
Because the concrete environments are different, it is
difficult to depict all the cases, so this paper only explains
these cases which the robot meets most frequently.
1 No obstacle in front of the robot, and the frontier edge
is integrated
If there is no obstacle in the front exploration area, and
the frontier edge is an integrated semi-circle as
described in Figure 2, the robot should keep the moving
direction unchanged, and select a location in front as
the candidate. Considering the environment information
losing, the distance between the robot current location
and candidate should be not large. After travelling
certain distance, robot needs to explore the surrounding
environment again.
As in Figure 2, when robot is located at position A, it
explores the environment and finds that the explored
area is free space, the frontier is an integrated
semi-circle. The robot keeps its moving direction and
travel certain distance to position B, explores the
environment again. Because the travel distance is not
far, the omitted environment information is not large,
so it does not influence the environmental traversal.
The distance between position A and B is related with
the laser scanner’s measure scope and can not adopt a
too large value.
2 Frontier is divided by obstacle
First we should determine how many segments of the
frontier divided by obstacle. Generally, we choose a
candidate on each continuous frontier. The number of
continuous frontier is same as that of the candidate. The
location of the candidate generally locates at the middle
position of the line made by the two end points of the
continuous frontier edge.
As described in Figure 3(a), the frontier is divided into
two parts by the yellow obstacle, one part is arc AB and
line BC, the other is line DE and arc EF. So we can
only select two candidates which locate on the middle
points of line AC and DF, denoted by o1 and o2,
respectively.
As shown in Figure 3(b), the frontier is divided into a
continuous one by the obstacle, so we can only select
one candidate, and the method is same as above.
The candidate locates at the middle point of the line
made by the two end points of the continuous
frontier. This case often exists in corridor or narrow
route-way.
3 No frontier in front of the robot
No frontier in front of the robot indicates that the robot
goes into a ‘dead end’, the front area is obstacle or
already known field. If there are candidates without
having been explored, the robot should move to these
candidates. If all the candidates are marked as explored,
the robot should end the exploration.