# Trace Target - The 2-D Target-Tracking Problem

A Target moving inside a polygon with *n* vertices which may contain holes. Compute the optimal motion of an observer,
that maintains line-of-sight visibility between the observer and the target. Our
algorithm computes an off-line strategy.

### Visibility

The
observer is assumed to be fitted with an idealized omnidirectional
sensor. Hence, a target is visible, if the line-of-sight between the target and
the observer is unobstructed.

### Optimality

An observer
path is optimal, if it is the shortest path *π*
among all possible paths that *t _{esc}* is maximized (escape time: the time, when the observer
first loss the target). For the cases when

*t*does not exist (i.e., the observer never loses track of the target), then the path

_{esc}*π*is optimal, if it minimizes

*t*(capture time: the time when the target is first captured). If a capture before

_{cap}*t*(stopping time of the target, i.e. the target has reached its target point) is not possible, then minimizes the final separation between the target and the observer.

_{stop}# Strategy

The
observer and the target have their own motion speeds and start points (motion
speeds and the start points could be same). The target has its motion path and
end point.

Define a
time length *dt*, e.g. 0.5 Second.

### Phase 1

If the
target moves around the corner of a hole, then the target is invisible, this
vertex we denote *E _{1}*. The time

*t*denotes the motion time of the observer from start point

_{0}*M*to the point, that the target is invisible. We draw a circle

_{0}*C*with the radius of the observer speed

_{0}*v*multiplied by time

_{obs}*t*centered at

_{0}*M*. Any sweeping lines

_{0}*l(*

*t)*connect the vertex

*E*and the target. The sweeping lines

_{1}*l(*

*t*intersect the circle

_{0})*C*in one or two points. We just need the nearest point

_{0}*a(*

*t*to the target. There is an angle

_{0})*θ(*

*t*between the segment

_{0})*M*and a vertical line. We draw a circle

_{0}a(t_{0})*C*with the same center of

_{1}*C*and radius of the observer speed

_{0}*v*

_{obs}*multiply by time*

*t*. The sweeping line

_{1}= t_{0}+ dt*l(*

*t*intersection the circle

_{1})*C*in one or two points. There is a point

_{1}*a(*

*t*and an angle

_{1})*θ(t*with

_{1})*θ(t*, we take the intersection point with angle

_{i+1})< θ(t_{i})*θ(t*, this point calls

_{i})*M*. The observer moves along a straight line to

_{1}*M*.

_{1}### Phase 2

### Leaning Curves

Draw a
circle of radius *v _{obs}*

*× dt*centered at

*M*. This circle intersects

_{1}*l(*

*t*(

_{M1}+ dt)*t*: the time, when the observer arrive at point

_{M1}*M*) at points

_{1}*b*and

_{1}*b*(

_{2}*b*is possible ). We get the arc

_{1}= b_{2}*b*above

_{1}b_{2}*l(*

*t*. We call the set of these points above

_{M1}+ dt)*l(*

*t*. Note the point

_{M1}+ dt), γ(t_{M1}+ dt)*b*, below which the target is not visible. Draw a ray with start point

_{1}*M*and through

_{1}*b*. We draw circles of radius

_{1}*v*

_{obs}*× dt*at points

*b*and

_{1}*b*, and a circle of radius

_{2}*v*

_{obs}*× 2dt*at point

*M*. Again, we consider the intersection of these circles with

_{1}*l(*

*t*and take all the points above

_{M1}+ 2dt)*l(t*. We get the set

_{M1}+ 2dt)*γ(*

*t*and the lower Point

_{M1}+ 2dt)*b*. Draw a ray with start point

_{3}*b*and through

_{1}*b*.

_{3}By
definition, if the observer moves along the leaning
curve the target will remain in sight. However, the observer may deviate from
the leaning curve before reaching *C _{1}*. This will happen, if the target
makes a turn around a second vertex

*C*:

_{2}### ρ-edge

We have now
many rays with start points *b _{1}, b_{3}, b_{5} ..., *and take a couple of special points on every
ray. The observer needs the same time from

*M*to arrive at each of the special points along the rays. The edge, which these points connect, at the time t, we call

_{1}*ρ(*

*t)*.

When the
target moves around the corner *C _{2}*
(invisible from observer), there are again leaning curves which have two
intersections with the ρ-edge. We consider just the nearer intersection to
the target. The first ray above it (we call that

*l*) has an angle

_{0}*φ(*

*l*a vertical line. After

_{0})*dt*time, there is another leaning curve

*l*, a nearer intersection, the first ray above it and a angle

_{1}*φ(*

*l*. These angles

_{1})*φ(*

*l*

_{i}*), i=0,1,2,*are monotone, w.l.o.g. monotonically increasing. When the first angle

*φ(*

*l*with

_{i+1})*φ(l*, we take the ray

_{i+1}) < φ(l_{i})*l*. Note

_{i}*M*the intersection from the ray

_{2}*l*

_{i}*and the ρ-edge*

*ρ(t*. The observer moves from

_{M1}+i*dt)*M*along the ray

_{1}*l*

_{i}*to the point*

*M*. Phase 2

_{2}*M*and

_{2}*C*has to be repeated until

_{2}- The target arrives at the end point, e.g. the target is always visible.
- The observer lost the target.

## Program:

We have implemented the Algorithm and applied this into two concrete examples. In our program the Phase 1 and Phase 2 will be put together into one Phase (Phase 2)

## Usage of the applet

Button Bsp1: | show the first example |

Button Bsp2: | show the second example |

Button TracePath: | show the calculated path of the tracking robot |

Button Run: | the robot and the target start to run |

Button >>: | the robot and the target run step by step |

Button clear: | open a new window |

Button Helpcurve: | show the help curves |

Literatur:

[1]: | A. Efrat, H. González-Banos, S. Kobourov, L. Palaniappan. Optimal Strategies to Track and Capture a Predictable Target |