[English] [Sitemap] [Über geometrylab.de]
	Startseite > Roboter-Bewegungsplanung > Roboterstrategien in Polygonen > Trace Target

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_esc does not exist (i.e., the observer never loses track of the target), then the path π is optimal, if it minimizes t_cap (capture time: the time when the target is first captured). If a capture before t_stop (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.

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₁. The time t₀ denotes the motion time of the observer from start point M₀ to the point, that the target is invisible. We draw a circle C₀ with the radius of the observer speed v_obs multiplied by time t₀ centered at M₀.  Any sweeping lines l(t) connect the vertex E₁ and the target. The sweeping lines l(t₀) intersect the circle C₀ in one or two points. We just need the nearest point a(t₀) to the target. There is an angle θ(t₀) between the segment M₀a(t₀) and a vertical line.  We draw a circle C₁ with the same center of C₀ and radius of the observer speed v_obs multiply by time t₁ = t₀ + dt. The sweeping line l(t₁) intersection the circle C₁ in one or two points. There is a point a(t₁) and an angle θ(t₁) with θ(t_i+1)< θ(t_i), we take the intersection point with angle θ(t_i), this point calls M₁. The observer moves along a straight line to M₁.

Phase 2

Leaning Curves

Draw a circle of radius v_obs × dt centered at M₁. This circle intersects l(t_M1 + dt) (t_M1: the time, when the observer arrive at point M₁) at points b₁ and b₂ (b₁ = b₂ is possible ). We get the arc b₁b₂ above l(t_M1 + dt). We call the set of these points above l(t_M1 + dt), γ(t_M1 + dt). Note the point b₁, below which the target is not visible. Draw a ray with start point M₁ and through b₁. We draw circles of radius v_obs × dt at points b₁ and b₂, and a circle of radius v_obs × 2dt at point M₁. Again, we consider the intersection of these circles with l(t_M1 + 2dt) and take all the points above l(t_M1 + 2dt). We get the set γ(t_M1 + 2dt) and the lower Point b₃. Draw a ray with start point b₁ and through b₃. 

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₁. This will happen, if the target makes a turn around a second vertex C₂:

ρ-edge

We have now many rays with start points b₁, b₃, b₅ ..., 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 ρ(t).

When the target moves around the corner C₂ (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 φ(l₀) a vertical line. After dt time, there is another leaning curve l₁, a nearer intersection, the first ray above it and a angle φ(l₁) …. These angles φ(l_i), i=0,1,2, … are monotone, w.l.o.g. monotonically increasing. When the first angle φ(l_i+1) with φ(l_i+1) < φ(l_i), we take the ray l_i. Note M₂ the intersection from the ray l_i and the ρ-edge ρ(t_M1+i*dt). The observer moves from M₁ along the ray l_i to the point M₂. Phase 2 M₂ and C₂ has to be repeated until

• 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

Literatur:

© Universität Bonn, Informatik Abt. I - - Letzte Änderung 02-08-2009 12:14