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.
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.
An observer path is optimal, if it is the shortest path π among all possible paths that tesc is maximized (escape time: the time, when the observer first loss the target). For the cases when tesc does not exist (i.e., the observer never loses track of the target), then the path π is optimal, if it minimizes tcap (capture time: the time when the target is first captured). If a capture before tstop (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.
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.
If the target moves around the corner of a hole, then the target is invisible, this vertex we denote E1. The time t0 denotes the motion time of the observer from start point M0 to the point, that the target is invisible. We draw a circle C0 with the radius of the observer speed vobs multiplied by time t0 centered at M0. Any sweeping lines l(t) connect the vertex E1 and the target. The sweeping lines l(t0) intersect the circle C0 in one or two points. We just need the nearest point a(t0) to the target. There is an angle θ(t0) between the segment M0a(t0) and a vertical line. We draw a circle C1 with the same center of C0 and radius of the observer speed vobs multiply by time t1 = t0 + dt. The sweeping line l(t1) intersection the circle C1 in one or two points. There is a point a(t1) and an angle θ(t1) with θ(ti+1)< θ(ti), we take the intersection point with angle θ(ti), this point calls M1. The observer moves along a straight line to M1.
Draw a circle of radius vobs × dt centered at M1. This circle intersects l(tM1 + dt) (tM1: the time, when the observer arrive at point M1) at points b1 and b2 (b1 = b2 is possible ). We get the arc b1b2 above l(tM1 + dt). We call the set of these points above l(tM1 + dt), γ(tM1 + dt). Note the point b1, below which the target is not visible. Draw a ray with start point M1 and through b1. We draw circles of radius vobs × dt at points b1 and b2, and a circle of radius vobs × 2dt at point M1. Again, we consider the intersection of these circles with l(tM1 + 2dt) and take all the points above l(tM1 + 2dt). We get the set γ(tM1 + 2dt) and the lower Point b3. Draw a ray with start point b1 and through b3.
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 C1. This will happen, if the target makes a turn around a second vertex C2:
We have now many rays with start points b1, b3, b5 ..., and take a couple of special points on every ray. The observer needs the same time from M1 to arrive at each of the special points along the rays. The edge, which these points connect, at the time t, we call ρ(t).
When the target moves around the corner C2 (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 l0) has an angle φ(l0) a vertical line. After dt time, there is another leaning curve l1, a nearer intersection, the first ray above it and a angle φ(l1) . These angles φ(li), i=0,1,2, are monotone, w.l.o.g. monotonically increasing. When the first angle φ(li+1) with φ(li+1) < φ(li), we take the ray li. Note M2 the intersection from the ray li and the ρ-edge ρ(tM1+i*dt). The observer moves from M1 along the ray li to the point M2. Phase 2 M2 and C2 has to be repeated until
- The target arrives at the end point, e.g. the target is always visible.
- The observer lost the target.
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|
|:||A. Efrat, H. González-Banos, S. Kobourov, L. Palaniappan. Optimal Strategies to Track and Capture a Predictable Target|