PAWS: A Deployed Application to Combat Poaching

PAWS – A Deployed Game-Theoretic Application to Combat Poaching

Fei Fang

, Thanh H. Nguyen

, Rob Pickles

, Wai Y. Lam

2,3

, Gopalasamy R. Clements

2,3,6

Bo An

, Amandeep Singh

, Brian C. Schwedock

, Milind Tambe

, Andrew Lemieux

{feifang,thanhhng,schwedoc,tambe}@usc.edu, University of Southern California, USA

[email protected], Panthera, USA,

[email protected], Rimba, Malaysia

[email protected], Nanyang Technological University, Singapore,

[email protected], Columbia University, USA

[email protected], Kenyir Research Institute, Universiti Malaysia Terengganu, Malaysia

alemieux@nscr.nl, The Netherlands Institute for the Study of Crime and Law Enforcement (NSCR), Netherlands

Abstract

Poaching is considered a major driver for the popula-

tion drop of key species such as tigers, elephants, and

rhinos, which can be detrimental to whole ecosystems.

While conducting foot patrols is the most commonly

used approach in many countries to prevent poaching,

such patrols often do not make the best use of the lim-

ited patrolling resources.

This paper presents PAWS, a game-theoretic applica-

tion deployed in Southeast Asia for optimizing foot pa-

trols to combat poaching. In this paper, we report on

the signiﬁcant evolution of PAWS from a proposed de-

cision aid introduced in 2014 to a regularly deployed

application. We outline key technical advances that lead

to PAWS’s regular deployment: (i) incorporating com-

plex topographic features, e.g., ridgelines, in generating

patrol routes; (ii) handling uncertainties in species dis-

tribution (game theoretic payoffs); (iii) ensuring scala-

bility for patrolling large-scale conservation areas with

ﬁne-grained guidance; and (iv) handling complex patrol

scheduling constraints.

Introduction

Poaching is a serious threat to wildlife conservation and can

lead to the extinction of species and destruction of ecosys-

tems. For example, poaching is considered a major driver

(Chapron et al. 2008) of why tigers are now found in less

than 7% of their historical range (Sanderson et al. 2006),

with three out of nine tiger subspecies already extinct (IUCN

2015). As a result, efforts have been made by law enforce-

ment agencies in many countries to protect endangered an-

imals from poaching. The most direct and commonly used

approach is conducting foot patrols. However, given their

limited human resources and the vast area in need of pro-

tection, improving the efﬁciency of patrols remains a major

challenge.

Game theory has become a well-established paradigm

for addressing complex resource allocation and patrolling

problems in security and sustainability domains. Models

and algorithms have been proposed and studied extensively

in the past decade, forming the general area of “secu-

rity games” (Tambe 2011). Furthermore, several security-

game-based decision support systems have previously been

 2016, Association for the Advancement of Artiﬁcial

successfully deployed in protecting critical infrastructure

such as airports, ports, and metro trains (Pita et al. 2008a;

Shieh et al. 2012; Yin et al. 2012). Inspired by the success of

these deployments, researchers have begun applying game

theory to generating effective patrol strategies in green se-

curity domains such as protecting wildlife (Yang et al. 2014;

Fang, Stone, and Tambe 2015), preventing over-ﬁshing

(Haskell et al. 2014; Qian et al. 2014) and illegal logging

(Johnson, Fang, and Tambe 2012).

Among these prior works, a novel emerging applica-

tion called PAWS (Protection Assistant for Wildlife Secu-

rity) (Yang et al. 2014) was introduced as a game-theoretic

decision-aid to optimize the use of human patrol resources

to combat poaching. PAWS was the ﬁrst of a new wave of

proposed applications in the subarea now called “green secu-

rity games” (Fang, Stone, and Tambe 2015; Kar et al. 2015).

Speciﬁcally, PAWS solves a repeated Stackelberg security

game, where the patrollers (defenders) conduct randomized

patrols against poachers (attackers) while balancing the pri-

orities of different locations with different animal densities.

Despite its promise, the initial PAWS effort did not test the

concept in the ﬁeld.

This paper reports on PAWS’s signiﬁcant evolution over

the last two years from a proposed decision aid to a regularly

deployed application. We report on the innovations made in

PAWS and lessons learned from the ﬁrst tests in Uganda

in Spring 2014, through its continued evolution since then,

to current deployments in Southeast Asia and plans for fu-

ture worldwide deployment. In this process, we have worked

closely with two non-government organizations (Panthera

and Rimba) and incorporated extensive feedback from pro-

fessional patrolling teams. Indeed, the ﬁrst tests revealed key

shortcomings in PAWS’s initial algorithms and assumptions

(we will henceforth refer to the initial version of PAWS

as PAWS-Initial, and to the version after our enhancement

as PAWS). First, a major limitation was that PAWS-Initial

ignored topographic information. Second, PAWS-Initial as-

sumed animal density and relevant problem features at dif-

ferent locations to be known, ignoring the uncertainty. Third,

PAWS-Initial could not scale to provide detailed patrol routes

in large conservation areas. Finally, PAWS-Initial failed to

consider patrol scheduling constraints.

In this paper, we outline novel research advances which

remedy the aforementioned limitations, making it possible

to deploy PAWS on a regular basis. First, we incorporate

elevation information and land features and use a novel hi-

erarchical modeling approach to building a virtual “street

map” of the conservation area. This virtual “street map”

helps scale-up while providing ﬁne-grained guidance, and

is an innovation that would be useful in many other do-

mains requiring patrolling of large areas. Essentially, the

street map connects the whole conservation area through

easy-to-follow route segments such as ridgelines, streams,

and river banks. The rationale for this comes from the fact

that animals, poachers, and patrollers all use these features

while moving. To address the second and third limitations,

we build on the street map concept with a novel algorithm

that uniquely synthesizes two threads of prior work in the

security games literature; speciﬁcally, the new PAWS algo-

rithm handles payoff uncertainty using the concept of min-

imax regret (Nguyen et al. 2015), while simultaneously en-

suring scalability – using our street maps – via the cutting

plane framework (Yang et al. 2013). Finally, we incorporate

into PAWS the ability to address constraints such as patrol

time limits and starting and ending at the base camp. In the

ﬁnal part of the paper, we provide detailed information about

the regular deployment of PAWS.

Background and Related Work

Criminologists have worked on the problem of combating

poaching, from policy design to illegal trade prevention

(Lemieux 2014). Geographic Information Systems (GIS) ex-

perts (Hamisi 2008) and wildlife management staff (Wato,

Wahungu, and Okello 2006) have carefully studied the iden-

tiﬁcation of poaching hotspots. In recent years, software

tools such as SMART (SMART 2013) and MIST (Stokes

2010) have been developed to help conservation managers

record data and analyze patrols retrospectively. We work on

a complementary problem of optimizing the patrol planning

of limited security staff in conservation areas.

In optimizing security resource allocation, previous work

on Stackelberg Security Games (SSGs) has led to many suc-

cessfully deployed applications for the security of airports,

ports and ﬂights (Pita et al. 2008b; Fang, Jiang, and Tambe

2013). Based on the early work on SSG, recent work has

focused on green security games (Kar et al. 2015), provid-

ing conceptual advances in integrating learning and plan-

ning (Fang, Stone, and Tambe 2015) and the ﬁrst applica-

tion to wildlife security PAWS-Initial. PAWS-Initial (Yang et

al. 2014) models the interaction between the patroller (de-

fender) and the poacher (attacker) who places snares in the

conservation area (see Figure 1) as a basic green security

game, i.e., a repeated SSG, where every few months, poach-

ing data is analyzed, and a new SSG is set up enabling im-

proved patrolling strategies. The deployed version of PAWS

adopts this framework.

We provide a brief review of SSGs, using PAWS as a

key example. In SSGs, the defender protects T targets from

an adversary by optimally allocating a set of R resources

(R < T ) (Pita et al. 2008b). In PAWS, the defender dis-

cretizes the conservation area into a grid, where each grid

cell is viewed as a target for poachers, to be protected by a

Figure 1: A picture of a

snare placed by poachers.

Figure 2: One patrol route

during the test in Uganda.

set of patrollers. The defender’s pure strategy is an assign-

ment of the resources to targets. The defender can choose a

mixed strategy, which is a probability distribution over pure

strategies. The defender strategy can be compactly repre-

sented as a coverage vector c = hc

i where c

is the cover-

age probability, i.e., the probability that a defender resource

is assigned to be at target i (Korzhyk, Conitzer, and Parr

2010). The adversary observes the defender’s mixed strat-

egy through surveillance and then attacks a target. An attack

could refer to the poacher, a snare, or some other aspect fa-

cilitating poaching (e.g., poaching camp). Each target is as-

sociated with payoff values which indicate the reward and

penalty for the players. If the adversary attacks target i, and

i is protected by the defender, the defender gets reward U

r,i

and the adversary receives penalty U

p,i

. Conversely, if not

protected, the defender gets penalty U

p,i

and the adversary

receives reward U

r,i

. U

r,i

is usually decided by animal den-

sity – higher animal density implies higher payoffs. Given

a defender strategy c and the penalty and reward values, we

can calculate the players’ expected utilities U

and U

when

target i is attacked accordingly.

In SSGs, the adversary’s behavior model decides his re-

sponse to the defender’s mixed strategy. Past work has of-

ten assumed that the adversary is perfectly rational, choos-

ing a single target with the highest expected utility (Pita et

al. 2008b). PAWS is the ﬁrst deployed application that re-

laxes this assumption in favor of a bounded rationality model

called SUQR, which models the adversary’s stochastic re-

sponse to defender’s strategy (Nguyen et al. 2013). SUQR

was shown to perform the best in human subject experi-

ments when compared with other models. SUQR predicts

the adversary’s probability of attacking i based on a linear

combination of three key features at the targets, including

the coverage probability c

, the attacker’s reward U

r,i

and

penalty U

p,i

. A set of parameters (w

, w

) are used for

combining the features. They indicate the importance of the

features and can be learned from data.

First Tests and Feedback

We ﬁrst tested PAWS-Initial (Yang et al. 2014) at Uganda’s

Queen Elizabeth National Park (QENP) for 3 days. Sub-

sequently, with the collaboration of Panthera and Rimba,

we started working in forests in Malaysia since September

(a) Deployed route (b) Patrollers

Figure 3: First 4-day patrol in Malaysia. Figure 3(a) shows

one suggested route (orange straight lines) and the actual pa-

trol track (black line). Figure 3(b) shows the patrollers walk-

ing along the stream during the patrol.

2014

. These protected forests are home to endangered ani-

mals such as the Malayan Tiger and Asian Elephant but are

threatened by poachers. One key difference of this site com-

pared to QENP is that there are large changes in elevation,

and the terrain is much more complex. The ﬁrst 4-day patrol

in Malaysia was conducted in November 2014. For this test,

we set the value of U

r,i

(input for PAWS-Initial) by aggregat-

ing observation data recorded during April 2014 - Septem-

ber 2014. We ﬁrst set the importance value of each cell as

a weighted sum of the observed counts of different types of

animals and different human activities. We then dilute the

importance value of available cells to nearby cells by apply-

ing a 5 by 5 Gaussian kernel for a convolution operation so

as to estimate the value for cells with no data recorded.

These initial tests revealed four areas of shortcomings,

which restricted PAWS-Initial from being used regularly and

widely. The ﬁrst limitation, which was surprising given that

it has received no attention in previous work on security

games, is the critical importance of topographic informa-

tion that was ignored in PAWS-Initial. Topography can af-

fect patrollers’ speed in key ways. For example, lakes are

inaccessible for foot patrols. Not considering such informa-

tion may lead to the failure of completing the patrol route.

Figure 2 shows one patrol route during the test in Uganda.

The suggested route (orange straight line) goes across the

water body (lower right part of ﬁgure), and hence the pa-

trollers decided to walk along the water body (black line).

Also, changes in elevation require extra patrol effort and

extreme changes may stop the patrollers from following a

route. For example, in Figure 3(a) [Malaysia], PAWS-Initial

planned a route on a 1km by 1km grid (straight lines), and

suggested that the patrollers walk to the north area (Row 1,

Column 3) from the south side (Row 2, Column 3). How-

ever, such movement was extremely difﬁcult because of the

changes in elevation. So patrollers decided to head towards

the northwest area as the elevation change is more gentle. In

addition, it is necessary to focus on terrain features such as

ridgelines and streams (Figure 3(b)) when planning routes

for three reasons: (i) they are important conduits for cer-

tain mammal species such as tigers; (ii) hence, poachers use

For the security of animals and patrollers, no latitude/longitude

information is presented in this paper.

(a) Ridgeline (b) Feasible routes (c) Coverage

Figure 4: Illustrative examples.

these features for trapping and moving about in general; (iii)

patrollers ﬁnd it easier to move around here than on slopes.

Figure 4(a) shows a prominent ridgeline.

The second limitation is that PAWS-Initial assumes the

payoff values of the targets — e.g., U

r,i

– are known and

ﬁxed. In the domain of wildlife protection, there can be un-

certainties due to animal movement and seasonal changes.

Thus, considering payoff uncertainty is necessary for opti-

mizing patrol strategy.

The third limitation is that PAWS-Initial cannot scale

to provide detailed patrol routes in large conservation ar-

eas, which is necessary for successful deployment. Detailed

routes require ﬁne-grained discretization, which leads to an

exponential number of routes in total.

The fourth limitation is that PAWS-Initial considers cov-

ering individual grid cells, but not feasible routes. In prac-

tice, the total patrolling time is limited, and the patrollers

can move to nearby areas. A patrol strategy for implementa-

tion should be in the form of a distribution over feasible pa-

trol routes satisfying these constraints. Without taking these

scheduling (routing) constraints into account, the optimal

coverage probabilities calculated by PAWS-Initial may not

be implementable. Figure 4(b) shows an example area that is

discretized into four cells and the base camp is located in the

upper left cell. There are three available patrol routes, each

protecting two targets. The coverage probabilities shown in

Figure 4(c) cannot be achieved by a randomization over the

three routes because the coverage of the upper left cell (Tar-

get 1) should be no less than the overall coverage of the re-

maining three cells since all routes start from the base camp.

PAWS Overview

Figure 5 provides an overview of the deployed version of

PAWS. PAWS ﬁrst takes the input data and estimates the an-

imal distribution and human activity distribution. Based on

this information, an SSG based game model is built, and the

patrol strategy is calculated. In wildlife protection, there is

repeated interaction between patrollers and poachers. When

patrollers execute the patrol strategy generated by PAWS

over a period (e.g., three months), more information is col-

lected and can become part of the input in the next round.

PAWS provides signiﬁcant innovations in addressing the

aforementioned limitations of PAWS-Initial. In building the

game model, PAWS uses a novel hierarchical modeling ap-

proach to building a virtual street map, while incorporating

detailed topographic information. PAWS models the poach-

ers bounded rationality as described by the SUQR model and

Calculate Patrol

Strategy

Build Game

Model

Initial Analysis

Input

Terrain

Information

Patrol Track

Observation Data

Street Map

Payoff

Uncertainty

Poacher

Behavior Model

ARROW

Human Activity

Distribution

Animal

Distribution

Route Generation

Cutting Plane

Execute and Collect Observations

Figure 5: PAWS Overview

considers uncertainty in payoff values. In calculating the pa-

trol strategy, PAWS uses ARROW (Nguyen et al. 2015) al-

gorithm to deal with payoff uncertainty and adopts cutting

plane approach and column generation to address the scala-

bility issue introduced by scheduling constraints.

Input and Initial Analysis

The input information includes contour lines which describe

the elevation, terrain information such as lakes and drainage,

base camp locations, previous observations (animals and hu-

man activities), as well as previous patrol tracks. However,

the point detections of animal and human activity presence

are not likely to be spatially representative. As such, it is

necessary to predict the animal and human activity distri-

bution over the entire study area. To this end, we used: 1)

JAGS (Plummer 2003) to produce a posterior predictive den-

sity raster for tigers (as a target species) derived from a

spatially explicit capture-recapture analysis conducted in a

Bayesian framework; and 2) MaxEnt (Phillips, Anderson,

and Schapire 2006) to create a raster of predicted human ac-

tivity distribution based on meaningful geographical covari-

ates (e.g., distance to water, slope, elevation) in a Maximum

Entropy Modelling framework.

Build Game Model

Based on the input information and the estimated distribu-

tion, we build a game model abstracting the strategic in-

teraction between the patroller and the poacher as an SSG.

Building a game model involves defender action modeling,

adversary action modeling, and payoff modeling. We will

discuss all three parts but emphasize defender action model-

ing since this is one of the major challenges to bring PAWS

to a regularly deployed application. Given the topographic

information, modeling defender actions in PAWS is far more

complex than any other previous security game domain.

Defender Action Modeling Based on the feedback from

the ﬁrst tests, we aim to provide detailed guidance to the pa-

trollers. If we use a ﬁne-grained grid and treat every ﬁne-

grained grid cell as a target, computing the optimal pa-

trolling strategy is exceptionally computationally challeng-

ing due to the large number of targets and the exponential

Figure 6: KAPs (black) for 2 by 2 grid cells.

number of patrol routes. Therefore, a key novelty of PAWS

is to provide a hierarchical modeling solution, the ﬁrst such

model in security game research. This hierarchical modeling

approach allows us to attain a good compromise between

scaling up and providing detailed guidance. This approach

would be applicable in many other domains for large open

area patrolling where security games are applicable, not only

other green security games applications, but others including

patrolling of large warehouse areas or large open campuses

via robots or UAVs.

More speciﬁcally, we leverage insights from hierarchical

abstraction for heuristic search such as path planning (Botea,

uller, and Schaeffer 2004) and apply two levels of dis-

cretization to the conservation area. We ﬁrst discretize the

conservation area into 1km by 1km Grid Cells and treat ev-

ery grid cell as a target. We further discretize the grid cells

into 50m by 50m Raster Pieces and describe the topographic

information such as elevation in 50m scale. The defender ac-

tions are patrol routes deﬁned over a virtual “street map” –

which is built in the terms of raster pieces while aided by

the grid cells in this abstraction as described below. With

this hierarchical modeling, the model keeps a small number

of targets and reduces the number of patrol routes while al-

lowing for details at the 50m scale.

The street map is a graph consisting of nodes and edges,

where the set of nodes is a small subset of the raster pieces

and edges are sequences of raster pieces linking the nodes.

We denote nodes as Key Access Points (KAPs) and edges

as route segments. The street map not only helps scalability

but also allows us to focus patrolling on preferred terrain fea-

tures such as ridgelines. The street map is built in three steps:

(i) determine the accessibility type for each raster piece, (ii)

deﬁne KAPs and (iii) ﬁnd route segments to link the KAPs.

In the ﬁrst step, we check the accessibility type of every

raster piece. For example, raster pieces in a lake are inacces-

sible, whereas raster pieces on ridgelines or previous patrol

tracks are easily accessible. Ridgelines and valley lines are

inferred from the contour lines using existing approaches in

hydrology (Tarboton, Bras, and Rodriguez-Iturbe 2007).

The second step is to deﬁne a set of KAPs, via which pa-

trols will be routed. We want to build the street map in such

a way that each grid cell can be reached. So we ﬁrst choose

raster pieces which can serve as entries and exits for the grid

cells as KAPs, i.e., the ones that are on the boundary of grid

cells and are easily accessible according to the accessibility

type calculated in the ﬁrst step. When there are multiple ad-

jacent raster pieces that are all easily accessible, we add the

midpoint as a KAP. If there are no easily accessible raster

pieces on one side of the boundary, we choose the raster

piece with the lowest slope as a KAP. In addition, we con-

sider existing base camps as KAPs as they are key points in

planning the patroller’s route. We choose additional KAPs

to ensure KAPs on the boundary of adjacent cells are paired.

Figure 6 shows identiﬁed KAPs and easily accessible pieces

(black and gray raster pieces respectively).

The last step is to ﬁnd route segments to connect the

KAPs. Instead of inefﬁciently ﬁnding route segments to con-

nect each pair of KAPs on the map globally, we ﬁnd route

segments locally for each pair of KAPs within the same

grid cell, which is sufﬁcient to connect all the KAPs. When

ﬁnding the route segment, we design a distance measure

which estimates the actual patrol effort and also gives high

priority to the preferred terrain features. The effort needed

for three-dimensional movement can be interpreted as the

equivalent distance on ﬂat terrain. For example, for gen-

tle slopes, equivalent “ﬂat-terrain” distance is obtained by

adding 8km for every 1km of elevation ascent according

to Naismith’s rule (Thompson 2011). In PAWS, we apply

Naismith’s rule with Langmuir corrections (Langmuir 1995)

for gentle slopes (< 20

◦

) and apply Tobler’s hiking speed

function (Tobler 1993) for steep slopes (≥ 20

◦

). Very steep

slopes (> 30

◦

) are not allowed. We penalize not walking on

preferred terrain features by adding extra distance. Given the

distance measure, the route segment is deﬁned as the short-

est distance path linking two KAPs within the grid cell.

The defender’s pure strategy is deﬁned as a patrol route on

the street map, starting from the base camp, walking along

route segments and ending with base camp, with its total dis-

tance satisfying the patrol distance limit (all measured as the

distance on ﬂat terrain). The patroller conﬁscates the snares

along the route and thus protects the grid cells. More specif-

ically, if the patroller walks along a route segment which

covers a sufﬁciently large portion (e.g., 50% of animal dis-

tribution) of a grid cell, the cell is considered to be protected.

The defender’s goal is to ﬁnd an optimal mixed patrol strat-

egy — a probability distribution over patrol routes.

Poacher Action Modeling and Payoff Modeling The

poacher’s actions are deﬁned over the grid cells to aid scala-

bility. In this game, we assume the poacher can observe the

defender’s mixed strategy and then chooses one target (a grid

cell) and places snares in this target. Following earlier work,

the poacher in this game is assumed to be boundedly ratio-

nal, and his actions can be described by the SUQR model.

Each target is associated with payoff values indicating

the reward and penalty for the patrollers and the poach-

ers. As mentioned earlier, PAWS models a zero-sum game

and the reward for the attacker (and the penalty for the de-

fender) is decided by the animal distribution. However, in

this game model, we need to handle uncertainty in the play-

ers’ payoff values since key domain features such as ani-

mal density which contribute to the payoffs are difﬁcult to

precisely estimate. In addition, seasonal or dynamic ani-

mal migration may lead to payoffs to become uncertain in

the next season. We use intervals to represent payoff un-

certainty in PAWS; the payoffs are known to lie within a

ARROW: compute optimal coverage vec-

tor

c given a set of linear constraints S.

Separation Oracle

Find Cutting Plane: Find a hyperplane

separating ˆc and feasible region C. If exists,

ˆc /∈ C and a new constraint s is found.

Route Generation: ﬁnd routes that

constitute the separation hyperplane.

Is ˆc ∈ C?

S = S ∪ s

Figure 7: New integrated algorithm

certain interval whereas the exact values are unknown. In-

terval uncertainty is, in fact, a well-known concept to cap-

ture uncertainty in security games (Nguyen et al. 2014;

2015). We determine the size of the payoff intervals at each

grid cell based on patrollers’ patrol efforts at that cell. If the

patrollers patrol a cell more frequently, there is less uncer-

tainty in the players’ payoffs at that target and thus a smaller

size of the payoff intervals.

Calculate Patrol Strategy

We build on algorithms from the rich security game liter-

ature to optimize the defender strategy. However, we ﬁnd

that no existing algorithm directly ﬁts our needs as we need

an algorithm that can scale-up to the size of the domain of

interest, where: (i) we must generate patrol routes over the

street map over the entire conservation area region, while

(ii) simultaneously addressing payoff uncertainty and (iii)

bounded rationality of the adversary. While the ARROW

(Nguyen et al. 2015) algorithm allows us to address (ii) and

(iii) together, it cannot handle scale-up over the street map.

Indeed, while the (virtual) street map is of tremendous value

in scaling up as discussed earlier, scaling up given all possi-

ble routes (≈ 10

routes) on the street map is still a massive

research challenge. We, therefore, integrate ARROW with

another algorithm BLADE (Yang et al. 2013) for addressing

the scalability issue, resulting in a novel algorithm that can

handle all the three aforementioned challenges. The new al-

gorithm is outlined in Figure 7. In the following, we explain

how ARROW and BLADE are adapted and integrated.

ARROW attempts to compute a strategy that is robust

to payoff uncertainty given that poachers’ responses follow

SUQR. The concept of minimizing maximum regret is a

well-known concept in AI for decision making under uncer-

tainty (Wang and Boutilier 2003). ARROW uses the solution

concept of behavioral minimax regret to provide the strategy

that minimizes regret or utility loss for the patrollers in the

presence of payoff uncertainty and bounded rational attack-

ers. In small-scale domains, ARROW could be provided all

the routes (the defender’s pure strategies), on the basis of

which it would calculate the PAWS solution – a distribu-

tion over the routes. Unfortunately, in large scale domains

like ours, enumerating all the routes is infeasible. We must,

therefore, turn to an approach of incremental solution gener-

ation, which is where it interfaces with the BLADE frame-

work.

More speciﬁcally, for scalability reasons, ARROW ﬁrst

generates the robust strategy for the patrollers in the form of

coverage probabilities over the grid cells without considera-

tion of any routes. Similar to BLADE, a separation oracle is

then called to check if the coverage vector is implementable.

If it is implementable, the oracle returns a probability distri-

bution over patrol routes that implements the coverage vec-

tor, which is the desired PAWS solution. If it is not imple-

mentable – see Figure 4(c) for an example of coverage vec-

tor that is not implementable – the oracle returns a constraint

(cutting plane) that informs ARROW why it is not. For the

example in Figure 4(b)-4(c), if ARROW generates a vec-

tor as shown in Figure 4(c), the constraint returned could

be c

≥

i=2

since all implementable coverage vector

should satisfy this constraint. This constraint helps ARROW

reﬁne its solution. The process repeats until the coverage

vector generated by ARROW is implementable.

As described in BLADE (Yang et al. 2013), to avoid enu-

merating all the feasible routes to check whether the cover-

age vector is implementable, the separation oracle iteratively

generate routes until it has just enough routes (usually after

a small number of iterations) to match the coverage vector

probabilities or get the constraint (cutting plane). At each

iteration of Route Generation (shown in the bottom-most

box in Figure 7), the new route is optimized to cover targets

of high value. However, we cannot directly use any exist-

ing algorithm to ﬁnd the optimal route at each iteration due

to the presence of our street map. But we note similarities

to the well-studied orienteering problem (Vansteenwegen,

Souffriau, and Oudheusden 2011) and exploit the insight of

the S-algorithm for orienteering (Tsiligiridis 1984).

In particular, in this bottom-most box of in Figure 7, to

ensure each route returned is of high quality, we run a lo-

cal search over a large number of routes and return the one

with the highest total value. In every iteration, we start from

the base KAP and choose which KAP to visit next through

a weighted random selection. The next KAP to be visited

can be any KAP on the map, and we assume the patroller

will take the shortest path from the current KAP to the next

KAP. The weight of each candidate KAP is proportional to

the ratio of the additional target value that can be accrued

and distance from current KAP. We set the lower bound of

the weight to be a small positive value to make sure every

feasible route can be chosen with positive probability. The

process continues until the patroller has to go back to the

base to meet the patrol distance limit constraint. Given a

large number of such routes, our algorithm returns a route

close to the optimal solution.

Integrating all these algorithms, PAWS calculates the pa-

trol strategy consisting of a set of patrol routes and the cor-

responding probability for taking them.

Addressing Additional Practical Challenges

We have introduced the technical innovations which lead to

PAWS’s deployment. In addition to these innovations, we

have addressed a number of practical constraints to make

the strategy suggested by PAWS easier to follow by human

patrollers. In this section, we summarize these challenges

and our solutions to them.

First, mountaintops should be considered as key points in

the patrol route. In PAWS, we require the patrollers always

move between KAPs, which are located at the boundary of

the grid cells or the base camps. Therefore, in some sug-

gested patrol routes, the patroller is asked to go to a moun-

taintop and go downhill for a short distance and then back-

track. However, this kind of short downhill followed by re-

turning uphill will annoy the patrollers, and they will natu-

rally ignore the downhill part. We address this problem by

considering mountain tops as KAPs when building the street

map. With these additional KAPs, patrollers are not forced

to take the short downhill unless necessary (i.e., 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 spend the time to record what they observe, includ-

ing 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 addi-

tion 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 ter-

rain features like ridgelines by designing a distance mea-

sure which penalizes not walking 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. In a

very hilly region of the area where there are large elevation

changes, the patrollers would highly prefer the terrain fea-

tures as it is much more easier to walk along them than tak-

ing 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 alterna-

tive route. To differentiate these different cases, we use sec-

ondary derivatives to check how important the ridgeline is.

Instead of penalizing not walking along the terrain features,

we can use a discount factor for taking the preferred route,

and assign a higher discount factor for terrain features with

a higher (regarding absolute value) secondary derivative.

Lastly, additional factors such as slope should be consid-

ered when evaluating the walking effort. In the distance mea-

sure introduced in the previous section, elevation change and

terrain features have been considered, but there are other fac-

tors that contribute to the walking effort. For example, walk-

ing 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 ﬂat terrain. Therefore, in the

distance measure, we penalize walking along hillside and

assign a higher penalty factor for a higher slope.

Trading Off Exploration and Exploitation

Building on the PAWS framework, we provide a variation

of PAWS (denoted as PAWS-EvE) which offers the option

of assigning a probability range for selecting an explorative

route. Explorative routes are those which cover a signiﬁcant

portion of previously unpatrolled land, while exploitative

routes are those which cover a signiﬁcant portion of land

previously patrolled.

The major advantage of selecting exploitative routes is

that patrollers are familiar with those patrol routes. Having

experience with the routes, patrollers also require less ef-

fort on following the routes as they would with unfamiliar

territory, enabling them to better cover the area they patrol.

Further, the explorative routes may require more effort on

checking the map, ﬁnding water reﬁll points, and ﬁguring

out the best way around unexpected obstacles. Some of these

tasks require experienced patrollers and additional equip-

ment which are not available for every patrol. However, if

patrollers were to only take exploitative routes, then poach-

ers would easily be able to observe such a strategy and then

focus on targeting other areas. With the objective of PAWS

to minimize poaching activity, it is necessary to also take

explorative routes. Therefore, offering the option of setting

a probability range for selecting an explorative route would

be helpful for practical use. The range is set before generat-

ing the patrols based on these practical concerns.

In order to implement the functionality of PAWS-EvE, we

modify the previously mentioned separation oracle by intro-

ducing two sets of routes, the explorative set and the ex-

ploitative set. Two new user-deﬁned parameters θ and δ are

introduced and we add two new constraints to make sure the

probability of assigning a patrol route from the explorative

set lies within a δ margin of θ. Also, in Route Generation,

we check if adding a route from the explorative set would

improve the solution, and then we also check if adding a

route from the exploitative set would improve the solution.

Deployment and Evaluation

PAWS patrols are now regularly deployed at a conservation

area in Malaysia. This section provides details about the de-

ployment and both subjective and objective evaluations of

PAWS patrols.

PAWS patrol aims to conduct daily patrols from base

camps. Before the patrol starts, PAWS generates the pa-

trol strategy starting from the base camp selected by patrol

team leader. The patrol distance limit considered by PAWS

is 10km per day (equivalent ﬂat terrain). As shown in Ta-

ble 1, this leads to about 9000 raster pieces to be consid-

ered. Thus, it is impossible to consider each raster piece as a

separate target or consider all possible routes over the raster

pieces. With the two-level discretization and the street map,

the problem scale is reduced, with 8.57(= 194.33/22.67)

KAPs and 80 route segments in each grid cell on average,

making the problem manageable. The strategy generated by

PAWS is a set of suggested routes associated with probabil-

ities and the average number of suggested routes associated

with probability > 0.001 is 12.

Each PAWS patrol lasts for 4-5 days and is executed by

Average # of Reachable Raster Pieces 9066.67

Average # of Reachable Grid Cells (Targets) 22.67

Average # of Reachable KAPs 194.33

Table 1: Problem Scale for PAWS Patrols.

Average Trip Length 4.67 Days

Average Number of Patrollers 5

Average Patrol Time Per Day 4.48 hours

Average Patrol Distance Per Day 9.29 km

Table 2: Basic Information of PAWS Patrols.

a team of 3-7 patrollers. The patrol planner will make plans

based on the strategy generated by PAWS. After reaching

the base camp, patrollers execute daily patrols, guided by

PAWS’s patrol routes. Table 2 provides a summary of basic

statistics about the patrols. During the patrol, the patrollers

are equipped with a printed map, a handheld GPS, and data

recording booklet. They detect animal and human activity

signs and record them with detailed comments and photos.

After the patrol, the data manager will put all the information

into a database, including patrol tracks recorded by the hand-

held GPS, and the observations recorded in the log book.

Figure 8 shows various types of signs found during the

patrols. Table 3 summarizes all the observations. These ob-

servations show that there is a serious ongoing threat from

the poachers. Column 2 shows results for all PAWS patrols.

Column 3 shows results for explorative PAWS patrols, the

(partial) patrol routes which go across areas where the pa-

trollers have never been before. To better understand the

numbers, we show in Column 4 the statistics about early-

stage non-PAWS patrols in this conservation area, which

were deployed for tiger survey. Although it is not a fair

comparison as the objectives of the non-PAWS patrols and

PAWS patrols are different, comparing Column 2 and 3 with

Column 4 indicates that PAWS patrols are effective in ﬁnd-

ing human activity signs and animal signs. Finding the hu-

man activity signs is important to identify hotspots of poach-

ing activity, and patrollers’ presence will deter the poachers.

Animals signs are not directly evaluating PAWS patrols, but

they indicate that PAWS patrols prioritize areas with higher

animal density. Finding these signs is aligned with the goal

of PAWS – combat poaching to save animals – and thus is

a proof for the effectiveness of PAWS. Comparing Column

3 with Column 2, we ﬁnd the average number of observa-

tions made along the explorative routes is comparable to and

even higher than that of all PAWS patrol routes. The obser-

vations on explorative routes are important as they lead to

a better understanding of the unexplored area. These results

show that PAWS can guide the patrollers towards hotspots

of poaching activity and provide valuable suggestions to the

patrol planners.

Along the way of PAWS deployment, we have received

feedback from patrol planners and patrollers. The patrol

planners mentioned that the top routes in PAWS solution

(routes with the highest probability) come close to an ac-

tual planner’s routes, which shows PAWS can suggest fea-

sible routes and potentially reduce the burden of the plan-

(a) Tiger sign (Nov. 2014) (b) Human sign (lighter; Jul.

2015)

camp; Aug. 2015)

(d) Human sign (tree marking;

Aug 2015)

Figure 8: Various signs recorded during PAWS patrols.

Patrol Type

All

PAWS

Patrol

Explorative

PAWS

Patrol

Patrol for

Tiger

Survey

Total Distance (km) 130.11 20.1 624.75

Average # of Human

Activity Signs per km

0.86 1.09 0.57

Average # of Animal

Signs per km

0.41 0.44 0.18

Table 3: Summary of observations.

ning effort. As we deploy PAWS in the future at other sites,

the cumulative human planners’ effort saved by using PAWS

will be a considerable amount. In addition, patrollers com-

mented that PAWS was able to guide them towards poach-

ing hotspots. The fact that they found multiple human signs

along the explorative PAWS patrol routes makes them be-

lieve that PAWS is good at ﬁnding good ridgelines that are

taken by animals and humans. Patrollers and patrol planners

also agree that PAWS generates detailed suggested routes

which can guide the actual patrol. Patrollers commented that

the suggested routes were mostly along the ridgeline, which

is easier to follow, compared with the routes from the ﬁrst

trial by PAWS-Initial. Figure 9 shows one suggested route

(orange line) and the actual patrol track (black line) during

PAWS patrol in Aug. 2015 (shown on 1km by 1km grid).

Due to the precision of the contour lines we get, we provide

a 50m buffer zone (light orange polygon) around the sug-

gested route (orange line). The patrollers started from the

basecamp (green triangle) and headed to the southeast. The

patrollers mostly followed PAWS’s suggested route, indicat-

ing that the route generated by PAWS is easy to follow (con-

trast with PAWS-Initial as shown in Figure 3(a)). Finally, the

power of randomization in PAWS solution can be expected

Figure 9: One daily PAWS Patrol route in Aug. 2015.

in the long-term.

Lessons Learned

During the development and deployment process, we faced

several challenges, and here we outline some lessons

learned.

First, ﬁrst-hand immersion in the security environment of

concern is critical to understanding the context and accel-

erating the development process. The authors (from USC

and NTU) intentionally went for patrols in the forest with

the local patrolling team to familiarize themselves with the

area. The ﬁrst-hand experience conﬁrmed the importance of

ridgelines, as several human and animal signs were found

along the way, and also conﬁrmed that extreme changes in

elevation require a considerable extra effort of the patrollers.

This gave us the insight for building the street map.

Second, visualizing the solution is important for commu-

nication and technology adaptation. When we communicate

with domain experts and human planners, we need to ef-

fectively convey the game-theoretic strategy generated by

PAWS, which is a probability distribution over routes. We

ﬁrst visualize the routes with probability > 0.01 using Ar-

cGIS so that they can be shown on the topographic map and

the animal distribution map. Then for each route, we pro-

vide detailed information that can assist the human planners’

decision-making. We not only provide basic statistics such

as probability to be taken and total distance, but also esti-

mate the difﬁculty level for patrol, predict the probability of

ﬁnding animals and human signs, and provide an elevation

chart that shows how the elevation changes along the route.

Such information can help planners’ understanding the strat-

egy, and also help the planner assign patrol routes to the right

team of patrollers, as some patrollers may be good at a long

distance walking with ﬂat terrain while others would prefer

short distance hiking with high elevation change.

Third, minimizing the need for extra equipment/effort

would further ease PAWS future deployment, i.e., patrollers

would prefer having a single handheld device for collect-

ing patrol data and displaying suggested patrol routes. If

PAWS routes could be embedded in the software that is al-

ready in use for collecting data in many conservation areas,

e.g., SMART, it would reduce the effort required of planners.

This is one direction for future development.

Summary

PAWS is a ﬁrst deployed “green security game” applica-

tion to optimize human patrol resources to combat poaching.

We provided key research advances to enable this deploy-

ment; this has provided a practical beneﬁt to patrol planners

and patrollers. The deployment of PAWS patrols will con-

tinue at the site in Malaysia. Panthera has seen the utility

of PAWS, and we are taking steps to expand PAWS to its

other sites. This future expansion and maintenance of PAWS

will be taken over by ARMORWAY (ARMORWAY 2015),

a “security games” company (starting in Spring 2016); AR-

MORWAY has signiﬁcant experience in supporting security-

games-based software deployments.

Acknowledgement

This research was supported by MURI Grant W911NF-11-

1-0332. And thanks to our partners in the ﬁeld who made

these tests possible.

References

ARMORWAY. 2015. http://armorway.com/.

Botea, A.; M

uller, M.; and Schaeffer, J. 2004. Near op-

timal hierarchical path-ﬁnding. Journal of Game Develop-

ment 1:7–28.

Chapron, G.; Miquelle, D. G.; Lambert, A.; Goodrich, J. M.;

Legendre, S.; and Clobert, J. 2008. The impact on tigers of

poaching versus prey depletion. Journal of Applied Ecology

45:16671674.

Fang, F.; Jiang, A. X.; and Tambe, M. 2013. Optimal patrol

strategy for protecting moving targets with multiple mobile

resources. In AAMAS.

Fang, F.; Stone, P.; and Tambe, M. 2015. When security

games go green: Designing defender strategies to prevent

poaching and illegal ﬁshing. In International Joint Confer-

ence on Artiﬁcial Intelligence (IJCAI).

Hamisi, M. 2008. Identiﬁcation and mapping risk areas for

zebra poaching: A case of Tarangire National Park, Tanza-

nia. Ph.D. Dissertation, Thesis, ITC.

Haskell, W. B.; Kar, D.; Fang, F.; Tambe, M.; Cheung, S.;

and Denicola, L. E. 2014. Robust protection of fsheries

with COmPASS. In IAAI.

IUCN. 2015. IUCN red list of threatened species. version

2015.2. http://www.iucnredlist.org.

Johnson, M. P.; Fang, F.; and Tambe, M. 2012. Patrol strate-

gies to maximize pristine forest area. In AAAI.

Kar, D.; Fang, F.; Fave, F. D.; Sintov, N.; and Tambe, M.

2015. A Game of Thrones: When human behavior models

compete in repeated Stackelberg security games. In AAMAS

2015.

Korzhyk, D.; Conitzer, V.; and Parr, R. 2010. Complex-

ity of computing optimal Stackelberg strategies in security

resource allocation games. In AAAI, 805–810.

Langmuir, E. 1995. Mountaincraft and Leadership: A

Handbook for Mountaineers and Hillwalking Leaders in the

British Isles. Mountain Leader Training Board.

Lemieux, A. M., ed. 2014. Situational Prevention of Poach-

ing. Crime Science Series. Routledge.

Nguyen, T. H.; Yang, R.; Azaria, A.; Kraus, S.; and Tambe,

M. 2013. Analyzing the effectiveness of adversary modeling

in security games. In AAAI.

Nguyen, T. H.; Yadav, A.; An, B.; Tambe, M.; and Boutilier,

C. 2014. Regret-based optimization and preference elici-

tation for Stackelberg security games with uncertainty. In

AAAI.

Nguyen, T. H.; Fave, F. M. D.; Kar, D.; Lakshminarayanan,

A. S.; Yadav, A.; Tambe, M.; Agmon, N.; Plumptre, A. J.;

Driciru, M.; Wanyama, F.; and Rwetsiba, A. 2015. Mak-

ing the most of our regrets: Regret-based solutions to handle

payoff uncertainty and elicitation in green security games.

In Conference on Decision and Game Theory for Security.

Phillips, S. J.; Anderson, R. P.; and Schapire, R. E. 2006.

Maximum entropy modeling of species geographic distribu-

tions. Ecological Modelling 190(3-4):231–259.

Pita, J.; Jain, M.; Marecki, J.; Ord

nez, F.; Portway, C.;

Tambe, M.; Western, C.; Paruchuri, P.; and Kraus, S. 2008a.

Deployed ARMOR protection: the application of a game

theoretic model for security at the Los Angeles International

Airport. In Proceedings of the 7th International Joint Con-

ference on Autonomous Agents and Multiagent Systems: In-

dustrial Track, AAMAS ’08, 125–132.

Pita, J.; Jain, M.; Western, C.; Portway, C.; Tambe, M.; Or-

donez, F.; Kraus, S.; and Paruchuri, P. 2008b. Deployed AR-

MOR protection: The application of a game theroetic model

for security at the Los Angeles International Airport. In AA-

MAS.

Plummer, M. 2003. JAGS: A program for analysis of

Bayesian graphical models using Gibbs sampling.

Qian, Y.; Haskell, W. B.; Jiang, A. X.; and Tambe, M. 2014.

Online planning for optimal protector strategies in resource

conservation games. In AAMAS.

Sanderson, E.; Forrest, J.; Loucks, C.; Ginsberg, J.; Din-

erstein, E.; Seidensticker, J.; Leimgruber, P.; Songer, M.;

Heydlauff, A.; OBrien, T.; Bryja, G.; Klenzendorf, S.; and

Wikramanayake, E. 2006. Setting priorities for the conser-

vation and recovery of wild tigers: 2005-2015. the techni-

cal assessment. Technical report, WCS, WWF, Smithsonian,

and NFWF-STF, New York Washington, D.C.

Shieh, E.; An, B.; Yang, R.; Tambe, M.; Baldwin, C.; Di-

Renzo, J.; Maule, B.; and Meyer, G. 2012. PROTECT:

A deployed game theoretic system to protect the ports of

the United States. In Proceedings of the 11th International

Conference on Autonomous Agents and Multiagent Systems

- Volume 1, AAMAS ’12, 13–20.

SMART. 2013. The spatial monitoring and reporting tool

(SMART). http://www.smartconservationsoftware.org/.

Stokes, E. J. 2010. Improving effectiveness of protection ef-

forts in tiger source sites: developing a framework for law

enforcement monitoring using mist. Integrative Zoology

5(4):363–377.

Tambe, M. 2011. Security and Game Theory: Algorithms,

Deployed Systems, Lessons Learned. Cambridge University

Press.

Tarboton, D. G.; Bras, R. L.; and Rodriguez-Iturbe, I. 2007.

On the extraction of channel networks from digital elevation

data. Hydrologic Processes 5(1):81–100.

Thompson, S. 2011. Unjustiﬁable Risk?: The Story of

British Climbing. Cicerone Press.

Tobler, W. 1993. Three presentations on geographical analy-

sis and modeling. non-isotropic geographic modeling: spec-

ulations on the geometry of geography, and global spatial

analysis (93-1). Technical report, UC Santa Barbara.

Tsiligiridis, T. 1984. Heuristic methods applied to orien-

teering. The Journal of the Operational Research Society

35(9):pp. 797–809.

Vansteenwegen, P.; Souffriau, W.; and Oudheusden, D. V.

2011. The orienteering problem: A survey. European Jour-

nal of Operational Research 209(1):1–10.

Wang, T., and Boutilier, C. 2003. Incremental utility elici-

tation with the minimax regret decision criterion. In IJCAI.

Wato, Y. A.; Wahungu, G. M.; and Okello, M. M. 2006.

Correlates of wildlife snaring patterns in tsavo west national

park, Kenya. Biological Conservation 132(4):500–509.

Yang, R.; Jiang, A. X.; Tambe, M.; and Ordonez, F. 2013.

Scaling-up security games with boundedly rational adver-

saries: A cutting-plane approach. In IJCAI.

Yang, R.; Ford, B.; Tambe, M.; and Lemieux, A. 2014.

Adaptive resource allocation for wildlife protection against

illegal poachers. In AAMAS.

Yin, Z.; Jiang, A. X.; Johnson, M. P.; Kiekintveld, C.;

Leyton-Brown, K.; Sandholm, T.; Tambe, M.; and Sullivan,

J. P. 2012. TRUSTS: Scheduling randomized patrols for fare

inspection in transit systems. In Proceedings of the Twenty-

Fourth Conference on Innovative Applications of Artiﬁcial

Intelligence (IAAI), 2348–2355.