=Paper=
{{Paper
|id=Vol-1662/mpr5
|storemode=property
|title=Dynamic programming and greedy heuristic in Camera Trap Traveling Salesman Problem
|pdfUrl=https://ceur-ws.org/Vol-1662/mpr5.pdf
|volume=Vol-1662
|authors=Yaroslav V. Salii,Evgenii E. Ivanko
}}
==Dynamic programming and greedy heuristic in Camera Trap Traveling Salesman Problem==
https://ceur-ws.org/Vol-1662/mpr5.pdf
Dynamic programming and greedy heuristic in Camera
Trap Traveling Salesman Problem
Yaroslav V. Salii Evgenii E. Ivanko
yvs314@gmail.com viatore@ya.ru
Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia)
Ural Federal University (Yekaterinburg, Russia)
Abstract
We consider a very weak version of 1-PDTSP related to one specific
problem of ordering a sequence of single-type objects, which stems
from the problem of rearranging camera traps to increase statistic
significance in problems of assessing animal population. Compared
with our previous version of dynamic programming, the dimension
of problem instances solved went up to 12 camera traps (25 cities
including the base) due to a leaner C++ implementation and the lack of
treatment of infeasible DP states. Feasibility of a dynamic programming
solution was studied analytically in view of the memory constraints,
i.e., we implemented an algorithm for calculating the number of states
for this problem and compared it with the corresponding traveling
salesman problem. For solving the problems of dimension greater than
12, we implemented a simple greedy heuristic, the quality of which
was compared with the exact algorithm for one hundred randomly
generated 12-camera trap problem instances.
1 Introduction
The problem under consideration consists of relocating several pre-installed single-type objects to designated new
installation sites, starting from some point of origin that does not coincide with either pre-installed objects or
new object positions, and returning there after the work is finished, all of this as fast as possible. It is almost the
same as the traveling salesman problem (TSP), its only difference being the obvious constraint of never visiting
a new installation site without at least one object “in the backpack.” The “backpack” is assumed to have infinite
capacity.
This problem was first formulated in [6] in view of a real-life problem that biologists who study animal
population dynamics face when trying to improve the statistical significance of animal population assessments
made with the aid of camera traps. A camera trap is sufficiently light to carry any reasonable amount in a
backpack, yet good camera traps are also too expensive to obtain in such an amount so as to remove the need to
relocate those already placed. Hence the need to consider exactly the problem we describe below; throughout the
paper, we will refer to our objects as camera traps, although it is of course applicable to other objects in similar
circumstances. In fact, this problem is a very weak version of 1-PDTSP (see, for example, [5]), with infinite
capacity and binary supply and demand.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the 47th International Youth School-conference “Modern Problems in
Mathematics and its Applications”, Yekaterinburg, Russia, 02-Feb-2016, published at http://ceur-ws.org
215
We propose an exact method of solving this problem, via dynamic programming (DP), and a simple greedy
heuristic. These methods are chosen over the more traditional and developed mixed integer-linear programming
because a) there is no actual need to solve really large problems optimally—relocating 12 camera traps is deemed
sufficient and b) they do not require expensive license fees of good linear programming frameworks.
2 Problem statement
Here and below, the symbol , denotes equality by definition; an ordered pair of two objects a and b is written
in parentheses, (a, b); and the power set of a set S is written P(S).
Denote the dimension of the problem, i.e., the number of cameras, by a natural N . The ground set is X ,
0, 2N = {0} ∪ R ∪ B, where the symbol 0 denotes the base (the point of origin and return), the set R , 1, N ,
|R| = N , contains the indices of extant camera trap locations, and the set B , N + 1, 2N , |B| = N , indexes the
new sites for the camera traps. For the sake of convenience, “extant camera trap locations” will be referred to as
red points, and “new camera trap locations” will be referred to as blue points. We will also avoid distinguishing
a point from its index where it will not lead to confusion.
The cost of moving between two points is defined through a function c : X × X → R. Each problem instance
is completely determined by the set X and the corresponding cost function c. A solution to a problem (X, c) is
a permutation of the indices 1, 2N , or a route; the set of all solutions is denoted by P. We will denote the routes
by lowercase Greek letters, and, in an expression of the form α(i) = j, the natural number j is an index of the
point that occupies the i-th position of the route α.
Since the agent may only visit a blue point with at least one camera trap “in his pack,” some routes will
inevitably be infeasible, e.g., the route that visits all blue points first. We must offer a means of distinguishing
between feasible and infeasible routes. For a DP solution, it is convenient to use a “feasible exit point operator”
I : P(X) → P(X) defined as follows:
(
K, |K ∩ R| > |K ∩ B|;
I(K) ,
K ∩ B, |K ∩ R| = |K ∩ B|.
Informally, it says that the last point of a route through K starting at 0 may be any color if there are more red
than blue points in K, but it must be a blue point if K has equal number of red and blue points. There may
never be more blue than red points in K because in this case the number of new camera trap sites is greater
than the number of camera traps collected.
With the aid of the operator I, the feasibility of a route is expressed by a gradual application of this operator
to the route’s “prefixes” (more formally, the set “supports” of these prefixes), and the set of all feasible routes is
defined as follows: n o
A , α ∈ P ∀s ∈ 1, 2N α(s) ∈ I α(t) : t ∈ 1, s .
Note that this is actually the same as a Dyck language, and the number of such routes is given by the N -th
Catalan number (see the references in [7]).
Finally, the quality of a feasible route α ∈ A is measured by the following additive quality criterion:
−1
n 2N o
C[α] , c 0, α(1) + c(i, i + 1) + c α(2N ), 0 ,
X
i=1
and the problem is to minimize it by choosing the best feasible route.
3 Dynamic programming
We employ a forward DP procedure not unlike [4] (and contrasting with the backward DP of [1]); this choice
is only a matter of preference—we find the forward procedure more straightforward for our particular problem.
Our notation is largely that of [3], with certain inconsequential tweaks to adapt it to the forward DP. For our
problem, this method was proposed in [6], with its validity proved by induction.
The principal idea of DP is to decompose a complex, intractable problem into a family of less complex
subproblems, from optimal solutions of which it is easy to obtain an optimal solution of the complete problem;
such subproblems are called the DP states.
216
In our case, a state is an ordered pair (K, x), where K ⊂ 1, 2N is called a task list, and x ∈ X \ K is the
terminal point. It describes the (sub)problem of visiting the points from K starting from the point of origin 0 and
finishing at the point x. In contrast with the ordinary TSP, not all such states are feasible, i.e., some subproblems
may not actually be solved without violating the condition of never visiting a blue point without a camera trap
in the pack, e.g., the state (B, 1).
In [6], infeasible states were assigned a cost of “infinity” (larger than any real cost possible). It is actually
possible to save both CPU cycles and storage space if, instead of making the cost of infeasible states “infinite,”
we could omit the treatment of these altogether. To this end, let us elaborate on a formal feasibility condition
for the states and a generation procedure that only produces the feasible ones.
A task list K ⊂ 1, 2N is called feasible if the number of blue points in it does not exceed the number of red
points; let us gather all such task lists into the set
n o
G , K ⊂ X |K ∩ R| ≥ |K ∩ B| .
We will find a use for a cardinality-wise partition of this set, Gi , K ∈ G |K| = i , i ∈ 0, 2N , with the empty
task list {∅} also deemed trivially feasible.
If a task list is feasible, it is still possible to “break” the state it would be a part of by choosing an inappropriate
terminal point. Obviously, if a task list K ∈ G has more red points than blue, i.e., after we finish it, we will still
have a camera trap to spare, we can choose any remaining point as the terminal. However, if all camera traps we
pick during our tour of K end being “used up” as we finish this tour (i.e., |K ∩ R| = |K ∩ B|), we must continue
to a red point to restock (with the obvious exception of K = R ∪ B, after which we only have to return to the
base). This is formally expressed through a feasible expansion operator J : G → X defined as follows:
(
X \ K, |K ∩ R| > |K ∩ B|;
J (K) ,
X \ K ∩ R, |K ∩ R| = |K ∩ B|;
we find it convenient to treat the case of K = R ∪ B separately, without resorting to the expansion operator.
The feasible expansion operator may also be defined through the feasible exit point operator I in the form
n o
J (K) = x ∈ (X \ K) x ∈ I K ∪ {x} ;
these are clearly equivalent, however, the direct definition helps to understand how exactly are feasible expansions
generated.
We are finally ready to formally define a feasible state. A state (K, x) is considered feasible if K ∈ G and
x ∈ J (K). Let us collect all the feasible states into the set
D , (K, x) : K ∈ G, x ∈ J (K) ,
which we partition by the cardinality of the task sets contained therein, ∀i ∈ 0, 2N − 1, Di , (K, x) : K ∈
Gi , x ∈ J (K) ; we call the elements of this partition the state space layers, or just layers. Since we avoided
dabbling with the base to prevent the clutter in our definition of J , we have to define the final layer separately,
D2N , (1, 2N , 0) . This one corresponds to the complete problem. Note also the initial layer D0 = (∅, x) :
x ∈ J (∅) , which contains the trivial subproblems of starting at the base 0 and finishing at some red x.
For each state (K, x) ∈ D, its value—the cost of optimally visiting K, with start at 0 and finish at x,— is
defined by the following recursive Bellman equation:
n o
v K \ {y}, y + c(y, x) ;
v(K, x) = min
y∈I(K)
v(∅, x) = c(0, x) ∀x ∈ R,
where the value of trivial
states from D0 serves as an initial condition. The value of the complete problem is
rendered as v 1, 2N , 0 . The validity of this equation clearly follows from the proof of a similar equation from
[6, Sect. 2.1].
The procedure of generating the feasible states D bottom-up and calculating their values is as follows:
217
1. Prime the algorithm with G0 = {∅}, G1 = R, and D0 . Note that the values v[D0 ] are already known.
2. For each l ∈ 1, 2N − 1
For each K ∈ Gl , for each x ∈ J (K),
• Add K ∪ {x} to Gl+1 .
• Add (K, x) to Dl . Calculate v(K, x) through the Bellman equation.
3. Calculate the final value v 1, 2N , 0 through the Bellman equation.
4. Recover an optimal route based on the values of v on D.
We will not elaborate on the recovery procedure used at stage 4 of this algorithm; its nothing new and was
discussed, for example, in [6, Sect 2.2].
4 Experiment
We analyzed 100 randomly generated problem instances with N = 12 camera traps (25 points including the
base) and compared the performance of the exact DP and greedy heuristic. The particular value of N was chosen
to reflect the problem of the greatest dimension the DP solution of which would not exceed 16GB of RAM at
the author’s PC. All data sets are available from the authors on request.
The exact DP algorithm took from 85 to 94 seconds to solve for each instance, while the time required by the
greedy heuristic was negligible. The performance gap (i.e, the ratio of the result of the greedy heuristic and the
result of the exact DP minus 1) was, on the average, 28%, with the minimum being 1%, maximum 81%, and
median 26%.
5 Space complexity of exact DP
Since our implementation of exact DP could not fit more than a 12-camera trap problem instance into the 16GB
available (a 12-camera trap instance consumed circa 12GB of RAM), we decided to try and calculate how many
states are actually feasible and compare this number with that of the corresponding TSP (i.e., we compared the
states count of our N -camera problem with 2N -city TSP).
It is not hard to calculate how many are there states in a TSP. In TSP, all task sets are feasible, and all
expansions are feasible too. Fix a number n. Then, the number of states is
n−1
X n
n
CTSP (n) = (n − i) + 1.
i=0
i n
Indeed, for i ∈ 0, n − 1, |Gi | = ni , and the number of terminal points is n − i; there is only one state in Dn ,
namely, (1, n, 0) is unique.
For our problem, this calculation is a bit more complex since a)some task lists are infeasible and b)some
expansions are not feasible (for certain feasible task lists of even cardinality, we can only expand into red points).
We find it impractical to provide a closed formula for our problem, but we will sketch its idea for a problem with
3 camera traps.
Consider the feasible task lists G0 , . . . , G6 . For G0 , we may choose neither a red nor a blue point, |G0 | = 30 30 ;
obviously, it may be expanded by any red point, thus,|D0 | = |R| = 3. Next, G1 has odd cardinality. Since we
only choose one point, it has to be red, thus, |G1 | = 31 30 ; in all task lists of G1 , there are more red than blue
points, hence, any of the remaining 2n − 1 points is a feasible expansion, |D1 | = 31 30 · 5. Let us pass to G2 .
We may either pick two red points, or one red and one blue, |G2 | = 32 30 + 31 31 . In the former case, we may
expand to any of the remaining 2n − 2points, however, in the latter, we have to go to a red point,
of which there
remains n − 1: |D2 | = 32 30 · 4 + 31 31 · 2. For G3 , we have |G3 | = 33 30 + 32 31 and |D3 | = 33 30 · 3 + 32 31 · 3.
Passing to G4 , we see |D4 | = 33 31 · 2 + 32 32 · 2; for D5 , we have |D5 | = 33 32 · 1, and D6 is a singleton,
|D6 | = 33 33 · 1.
The procedure for calculating the number of states for our problem was coded in Haskell. We also calculated
the ratio between CTSP (2n) and |D| for n-camera trap problem. It starts at 1.666 for 1 camera trap (2 TSP
cities, not counting the base), goes up to 1.941 for 2 camera traps (4 TSP cities, not counting the base), and has
six nines after the point as early as for 9 camera traps (18-city TSP).
218
6 Conclusions
We studied a rather weak variety of 1-PDTSP and proposed two palatable methods of solving it; we also found
out it is about twice as easy as a comparable TSP in terms of DP state count. The dimension of problems solved
was doubled in comparison with our previous attempt [6].
Our future work on similar problems has several objectives. The first one is to develop a software for planning
multiple camera trap relocations through a GIS so as to integrate this function into a GPS navigation device.
The second one is to deal with more constraints that arise in the field—typically, one hopes to complete the
relocations during the day’s sunlight hours. However, in case of a great number of camera traps or rough terrain
it may be impossible. To automate the planning procedure, we intend to adopt certain features of Orienteering
Problem or Team Orienteering Problem (see, for example, [2]).
References
[1] R. Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM
(JACM), 9(1):61–63, 1962
[2] I. M. Chao, B. L. Golden, E. A. Wasil. The team orienteering problem. European journal of operational
research, 88(3):464–474, 1996
[3] A. G. Chentsov. Extremal problems of routing and scheduling: a theoretical approach. Regular and Chaotic
Dynamics, 2008 (in Russian). = А. Г. Ченцов. Экстремальные задачи маршрутизации и распределения
заданий. Вопросы теории. «Регулярная и хаотическая динамика», 2008.
[4] M. Held, R. M. Karp. A dynamic programming approach to sequencing problems. Journal of the Society
for Industrial & Applied Mathematics, 10(1):196–210, 1962
[5] H. Hernández-Pérez, J. J. Salazar-González. A branch-and-cut algorithm for a traveling salesman problem
with pickup and delivery. Discrete Applied Mathematics, 145(1):126–139, 2004.
[6] E. Ivanko. Dynamic programming in a problem of rearranging single-type objects. Trudy Inst. Mat. i Mekh.
UrO RAN, 19(4):125–130, 2013 (in Russian). = Е. Иванко. Динамическое программирование в задаче
перестановки однотипных объектов. Тр. ИММ УрО РАН, 19(4):125–130, 2013.
[7] J. Labelle, Y. N. Yeh. Generalized Dyck paths. Discrete mathematics, 82(1):1–6, 1990.
219