IEEE Robotics & Automation Magazine - December 2022 - 152

for the robot to avoid obstacles while
reaching a selected gap goal. The
approach takes advantage of the fact
that gaps start and end at discontinuities
in the laser scan and leverages this principle
to find intermediate gap goals for
navigation. Let
pp ,
ii R1+ ! be adja2
cent
points in the laser scan and R
denote the maximum sensing range of
the lidar. The first discontinuity,
referred to as type 1, occurs when the
distance between the adjacent readings
is larger than the circumscribed diameter
dr
of the robot: pp d .2 r
ii 1 2
- +
The second discontinuity, type 2, occurs
when one of the two readings is
outside the lidar's sensing range:
.
ir $$5
+ --2
2 ir1
,
2
1 22
tinuity is referred to as rising; otherwise,
it is falling. In the following, we describe
how to leverage these discontinuities to
identify gaps.
The first step in gap detection is to
perform a forward pass from p0
in the laser point cloud scan
to
pn 1for
rising type 1 and type 2 discontinuities.
Let pi
denote the location
of the first rising discontinuity and
L {, ,}.in
+ =+11f - This point be -
comes the beginning of the gap. To
determine the end, we find the point pj
closest to pi
such that L . That is,
j ! +
pp p
j L+
j
=!
argmin
ij 2
.
(1)
The process continues, starting from
p .
j 1+ Once the forward pass is compx
Rp xR If--+
px pxir ir the disconpn
1to
p0 is done to find gaps via fall(,
), a tuple of
ga bii i
=
which keeps track of
with g)
ing discontinuities. At each detected
gap, defined as
the start and end points is added to a
quadtree T ,g
where all previously identified and visited
gaps are located. If any gap already
exists in the tree, it is ignored.
Once Tg
is updated, a gap Tg) !
g
is selected to be the intermediate goal if
it is determined that the final goal x)
is
not admissible. In this context, admissibility
is determined by checking
whether a given goal is navigable; that
is, from the laser scan data, a path is
known to exist from the robot position
to the goal. The check is done by using
a similar algorithm, as discussed by
Minguez and Montano, which, given
any start point xa
and endpoint x ,b
ensures that no inflated obstacles block
the robot along the line connecting the
two points.
The process to select the gap goal
from Tg
when x)
is inadmissible is
outlined in Algorithm 1. At each iteration,
the algorithm finds the closest gap
g)
to the final goal x .) If g)
is inadmissible
from the robot's current position,
properties of quadtree queries are utilized
to find all gaps TG
g
robot that is also admissible to ,g)
meaning that the robot knows that a
feasible path from xr
plete, a mirrored backward pass from for the given ,g)
x∗
g1
g
g2
g3
do
θdes
xr
(a)
(b)
Figure 4. Examples of the UVA team's (a) detected gaps in a simulated BARN
environment and (b) local planner obstacle avoidance.
152 * IEEE ROBOTICS & AUTOMATION MAGAZINE * DECEMBER 2022
θo
D
θg
do
l 3 that must
to
as the next-closest gap to ,x)
and terminates once an admissible gap
is found. For clarity, Figure 4(a) gives
an example of the goal selection process.
The final goal x)
is not admissible,
nor is the closest gap to it, g .1 However,
xr to g2 is admissible as well as g2
g .1 Thus, g2
to
is selected as the intermediate
goal, and the selection process
repeats once the robot reaches
g .2
Even though the selected gap goal is
admissible, a direct path to it may not
be feasible given the configuration of
the obstacles within an environment.
For example, a robot navigating directly
to g in Figure 4(b) will collide with the
obstacles shown by the laser scan data.
To prevent such issues from arising, a
local planner is utilized that replans the
mobile robot's trajectory at every time
step if collision is imminent. The direct
path to the goal is formulated as a
region D, which accounts for the relative
heading to the goal,
ig , and the
diameter dr of the robot. The region D
is checked against the laser scan points
for any obstacles. Let p represent all
obstacle coordinates within region D. If
no obstacles are in D, that is,
p ,4=
be passed as the robot drives from xr
g .) The algorithm then iteratively finds
the closest admissible gap gG! l to the
to g and from g to
g) exists. If no g satisfies this constraint
the process repeats,
x∗
the robot is sent directly to the gap goal,
g. If there are multiple obstacles within
D, the one closest to the robot is
selected. Let do
represent the distance
to the closest obstacle and oi represent
the direction of the obstacle with
respect to the robot's heading. The new
desired heading is then computed by
accounting for the offset between the
Algorithm 1: Find Gap Goal
(UVA Team)
1: Input: quadtree
T ,g
2: Output: gap goal g)
3: while Tg
do
4: gx g 2
5: TT \ {})ggg
))- )
g
! argming T) !
!
6: # Returns children in descending
order of dist. to xr
7: Gg T )
l
! getChildren rg
)
(, ,
x
8: for gG! l do
9:
10: gg=)
11:
end if
12: end for
13: end while
14: return g)
if isAdmissibl (, )xge r
isAdmissibl (, )gge
)
&
then
x ,r and final goal x)
= 4Y &
robot position
!isAdmissibl (, )xge r
)
IEEE Robotics & Automation Magazine - December 2022

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - December 2022
