camps. Therefore, in some suggested patrol routes,
the patroller is asked to go to a mountaintop and go
downhill for a short distance and then backtrack.
However, this kind of short downhill followed by
returning uphill will annoy the patrollers, and they
will naturally ignore the downhill part. We address
this problem by considering mountaintops as KAPs
when building the street map. With these additional
KAPs, patrollers are not forced to take the short
downhill unless necessary (that is, when the short
downhill covers areas with high animal density).
Second, there is a limit on working time in addition to the limit on walking distance. It takes less
time for the patroller to go to an area and then backtrack than to take a loop even if the walking distance
is the same. The reason is the patrollers need to spend
the time to record what they observe, including animal signs and human activity signs. If the patrollers
walk along the same ridgeline twice in a day, they
only need to record the signs once. Therefore, in
designing the patrol routes, we should consider the
total working time in addition to the total distance.
This is implemented in PAWS by adding additional
constraints in route generation.
Third, not all terrain features should be treated in
the same way. In building the street map, we give
preference to terrain features like ridgelines by
designing a distance measure that penalizes not walk-
ing along the terrain feature. However, how much
priority should be given to the terrain features
depends on the cost of the alternative routes, or how
much easier it is compared to taking other routes. On
the one hand, in a very hilly region of the area where
there are large elevation changes, the patrollers
would highly prefer the terrain features as it is much
easier to walk along them than taking an alternative
route. On the other hand, if the elevation change in
the region is small, the effort of taking a ridgeline for
unit distance is comparable to that of taking an alter-
native route. To differentiate these different cases, we
use secondary derivatives to check how important
the ridgeline is. Instead of penalizing not walking
along the terrain features, we can use a discount fac-
tor for taking the preferred route, and assign a high-
er discount factor for terrain features with a higher
(regarding absolute value) secondary derivative.
Finally, additional factors such as slope should be
considered when evaluating the walking effort. In
the distance measure introduced in the previous section, elevation change and terrain features have been
considered, but there are other factors that contribute to the walking effort. For example, walking
along the contour line will lead to zero elevation
change along the way, but the effort needed highly
depends on the slope. Walking along the hillside of a
steep slope takes much more effort than walking on
the flat terrain. Therefore, in the distance measure,
we penalize walking along the hillside and assign a
higher penalty factor for a higher slope.
Trading Off Exploration and Exploitation
Building on the PAWS framework, we provide a vari-
SPRING 2017 31
Figure 7. New Integrated Algorithm.
S = S ∪ s
ARROW: compute optimal coverage
vector c given a set of linear constraints S. ˆ
Route Generation: ;nd routes that
constitute the separation hyperplane.
FindCuttingPlane: Find a hyperplane
separating c and feasible region C. If exists,