Abstract:
One of the means to observe wild animals in their natural habitat is the camera trap; the latter are used, in particular, to study the populations of wild animals. There are reasons to believe that it is worthwhile to periodically rearrange the camera traps, whence the three problems. The first one is to calculate the distances between prospective camera locations in view of the terrain; this problem is beyond the scope of our talk.
The second problem is to determine an optimal route of moving N (where N is a natural number) cameras to N new locations. This is problem is related to the TSP, however, it has the following natural constraint likening it to the various Vehicle Routing Problems: when visiting a new camera location, the agent must have at least one camera with him. This constraint makes a dynamic programming solution of this problem less complex than the corresponding TSP of the same dimensionality due to lesser state space cardinality.
The third problem is to plan several camera rearrangements in advance, where the distance between two camera arrangements is the optimal cost of moving cameras from arrangement one to arrangement two, where each such route starts at a special point where there are no cameras (the base) and return to the base is mandated at its end. This results into a TSP on arrangements, however, there are reasons to believe that it might be prudent to use the bottleneck quality criterion and not the usual additive one.
|
