oc.optimization control - Trawler Problem

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 $2pi 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} > 2pi 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 $2pi 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