Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have an N-D optimal search problem that closely resembles the so-called Trawler Problem. [c.f. http://mathworld.wolfram.com/TrawlerProblem.html - though, the references cited there do not in fact address the Trawler problem.]

The search space is statistical, not spatial, but it can be partitioned and mapped into Cartesian coordinates for lower dimensional covariance projections.

Specifically, I am looking for the derivation of the solution to this Trawler problem. A Logarithmic Spiral, supposedly, centered on the covariance area. Useful references or pointers to this solution will be appreciated.


Add_comment to the most recent answer is not responding - so I am commenting using edit on the original question:


Thanx for your replies!

For the trawler problem itself, it is a straightforward construct to get the following integral- differential equation in polar coordinates:

r(theta) = rc – (vt/vs) Integral{Sgrt[r(theta)^2 + r’(theta)^2]} dtheta

With: r(theta) the radius from the center of the search area (the projected location of the object one is looking for – i.e. the center of the un-biased propagated search object covariance), rc the maximum searchable radius based on tracked object and search speeds (this is the containment radius – the searcher will encounter the object with probability 1 if the searcher stays on this closed perimeter – the search object will eventually cross this boundary), and the radical is the arc length of the search path, whatever it turns out to be.

Vt and Vs are the object and the search speeds respectively. If we let Vs be a constant this becomes a Volterra Equation of the Second Kind.

I can verify a logarithmic spiral does indeed solve this equation, with exponent vt/sgrt[vs^2 – vt^2). So does an inverse logarithmic spiral. But is that the general solution?

In retrospect I probably could have simply asked how to solve this integral equation. My Calculus of Variations is a bit rusty.

eta: Sorry, also having trouble with unicodes - coming out as gibberish. Will check into that.


If the search speed can be varied, the optimal path is an Archimedian Spiral. I can get to that solution fairly easily. Still no joy proving optimality of the Logrithmic Spiral though.

share|improve this question
    
Would you be able to provide a mathematical sketch of the problem, perhaps working backwards from the source code on this page (demonstrations.wolfram.com/TrawlerProblem) for the spatial, and see how far you get before you get stuck? That would help those of us who aren't familiar with the trawler problem to provide pointers on how to proceed. –  Gilead Aug 12 '10 at 1:53
    
The logarithmic spiral equation is usually given as r = ae**(btheta). You say that: "I can verify a logarithmic spiral does indeed solve this equation, with exponent vt/sgrt[vs^2 – vt^2)." Are you saying that b = vt/sqrt[vs2 - vt2] in the equation form that I gave above? I have been trying to derive b in this trawler problem for a while. If anyone knows what b is in terms of the speed of the pursuer and the speed of the boat being pursued, many thanks for posting. –  user14586 Apr 21 '11 at 17:09

1 Answer 1

I made some mistakes on my last write-up. I've corrected them below:

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The concept is fairly simple, and is explained here with some graphics to boot, but doesn't give a description of how to derive the solution.

I was thinking of the problem from the perspective of an interception, but this is a pursuit problem as stated on that page. The interception problem would work in essentially the same fashion:

  • Initial conditions and parameters:
    • Max speed of your boat
    • Position of your boat when target was last seen
    • Max speed of target
    • Last known position of target
    • The target will move in some unknown, unwavering direction at a constant speed
  • Assume the target heads directly toward you, and move to intercept on this trajectory
  • Assuming the target is not at this point, turn left or right and move along a path that keeps you on the perimeter of a circle whose radius is expanding from the last point you saw the target, and the rate of change of the radius is constant -- the max speed of the target
  • The nearer your speed is to the target's speed, the closer your trajectory gets to being perpendicular to the tangent of the circle

There's also a small snag that's not altogether obvious. Since these increasingly larger circles have a radius changing at a constant speed, $C_{s}$, the circumference is changing at a rate of $2\pi C_{s}$. If your boat doesn't move faster than this pace, you'll never complete a single revolution (break-even is around $6.29 C_{s}$).

A system describing the solution to that particular problem would probably look like this:

  • $t_0$ -- the time when the target is at the initial point
  • $t_1$ -- the time it would take for the slow & fast boat to meet if they moved toward each-other
  • $r'(t) = C_{s}$ -- speed of slow boat
  • $s'(t) = C_{f} > 2\pi C_{s}$ -- speed of fast boat
  • $s(t) = \int_{t_0}^t \sqrt{r'(t)^2 + (r(t) \theta'(t))^2} dt$
  • $r(t_0) = 0$
  • $(r(t_1), \theta(t_1)) = (r_{intercept}, \theta_{intercept})$
    • Coordinates where the two will intercept if they head toward each-other

Since $s'(t)$ is constant, then $s(t)$ is linear, implying the integrand in the arc-length expression will be constant. Using the fundamental theorem of calculus:

$s'(t)^2 = C_{f}^2 = C_{s}^2 + r(t)^2 \theta'(t)^2$
$\theta'(t) = \frac{1}{r(t)} \sqrt{C_{f}^2 - C_{s}^2}$

So, that's the motivation behind the solution they state on the Wolfram site, and a possible path behind its derivation, but it provides no means of stating that this solution is the optimal solution. No 'better' solution occurs to me, but that's not a proof.

The shortest path that gets your boat onto the expanding circle is to just move toward the initial point as described above, then continue to stay on the circle as it expands. Other than silly variations (eg, weaving around in a pattern that keeps you roughly r(t) units away from the target's initial position), I don't see any other solution that would result in you staying on the circle, moving around the initial target position, and not be a logarithmic spiral.

For the problem you're working on, you said it's nD. That presents a problem. In 2d I can stay on a circle, but in 3D there's an ever-expanding sphere (or hypersphere in nD).

The 2d version is solvable because you're moving around a growing circle, and you'll eventually encounter the point on this circle where the target is located. In $R^3$, you're a point moving around the surface of an expanding sphere. This is on par with asking what the probability is of hitting a particular point on a dart board -- and the answer is zero.

note: I think what I outline below with the planes & whatnot is screwy, looking back. Take it with a grain of salt.

Now, suppose you choose an arbitrary plane that intersects the center of the sphere, and follow the logarithmic spiral solution in this plane. As you move around the sphere, imagine a 2nd plane intersecting the center of the sphere [roughly] perpendicular to your current trajectory.

If you have the means to know whether your target is in the 2nd plane as you rotate around the sphere -- now the problem is on par with the 2d version because the plane will never 'pass over' the target as you rotate around the sphere.

Once you find a plane containing the target, the target must stay in this plane because the plane intersects the center of the sphere, and the target has been moving away from the center along a straight path. Start following a new logarithmic spiral from your current position, but staying in the 2nd plane, and you'll eventually catch your target.

The problem I mentioned earlier about your speed as compared to the target is similar in this case. In the worst case, you'd go just short of half way around the sphere and find a plane your target resides in, then a full revolution around the sphere and catch him near your starting position in the 2nd plane. In each case, you were staying on the perimeter of circles, so I'm confident that the same condition holds for your velocity as compared to the target -- you need to be traveling at a minimum speed of $2\pi C_s$ to catch your target.

Another variation in the $R^3$ case would be to define a small sphere around you, and if the target comes within that sphere then the search is over with. This sphere will intersect the larger sphere in a circular patch on the sphere's surface. Your search path would then be one that ensures there is a tiny overlap with previously traversed sections of the sphere until the entire surface area has been covered. Then you need to take into account the rate of expansion of the surface area to determine the necessary conditions (your speed and the size of your search 'bubble') for you to outpace the expansion rate. -Brian

share|improve this answer
    
Gilead, There's also a short description of the problem here: blog.wolfram.com/… The original problem statement went something like this: an object of interest (a body, drugs, a treasure chest; whatever) is dumped in the ocean at a particular location, and the individuals responsible soon leave. You arrive just in time to see them pull away. Luckily you brought a trawler with you to trawl the ocean floor to see what they dumped overboard, the problem is with ocean currents random drift <next> –  Brian Vandenberg Aug 13 '10 at 8:07
    
... random drift, etc, the object won't necessarily be directly below where they dumped it overboard. If you move to the initial drop point, estimate the speed of the ocean current, then move in a logarithmic spiral outward away from the initial drop point at a pace such that your change in radius is roughly equal to the speed of the ocean current, then after only one revolution around the starting point you have a very high likelihood of having netted the object in question. –  Brian Vandenberg Aug 13 '10 at 8:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.