Many applications require continuous monitoring of a moving target by a controllable vision system. Visual servos usually ignore the presence of obstacles and focus on imaging and target recognition issues. For a target moving among obstacles tracking is quite complex: a controllable observer (e.g., a robot) must anticipate that the target may become occluded by an obstacle and move to prevent such an event from occurring. And if the target’s intention is unknown the tracker has to be quite reactive in its decisions.
This an old project from 2001. The robots were from Nomadic Technologies, a robotics company whose products are long gone from the market. It is an old project, but the approach is still interesting because it combines a combinatorial motion planning technique into a real-time continuous controller. It is combinatorial in the sense that the algorithm explicitly computes a description of the geometric arrangement between the target and the observer’s visibility region produced by the local obstacles. But the algorithm also computes a continuous control law based on this description.
Here is an example of the tracker in action:
The project later became US patent 6,917,855, and published in ICRA 2002 (Real-time Combinatorial Tracking of a Target Moving Unpredictably Among Obstacles).
The system uses a LIDAR to acquire instant measurements of the target’s position and the location of the local obstacles. With this data a local visibility map is computed, and within this map the escape-path tree is computed.
Every path along the escape tree represents the shortest escape path (SEP) between the current target position and a free edge in the observer’s visibility region. The length of a given SEP is the shortest distance to escape (SDE) through the corresponding free edge.
The escape tree is thus an instantaneous description of the possible ways an antagonistic target can quickly escape the observer’s view.
The algorithm estimates the escape risk for every free edge as follows:
where c and m are constants, ro is the distance to observer to the corner causing the occlusion at said free edge, and h is the distance along the corresponding path in the escape tree. Minimizing ro increases the observer’s ability to track in the future, whereas maximizing h decreases the current likelihood that the target escapes.
It turns out the gradient of the risk can be explicitly computed. For example, given the arrangement shown the gradient is the following:
Because the gradient is computed analytically, only current sensor information is required. The tracking strategy consists of moving the observer in the opposite direction of the average of the gradient over all free edges in the observer’s visibility region. Note that this implements a continuous feedback controller.
The following example shows the transient response of the target tracker. it shows two experiments that differ only on the presence of a single occluding object. In the second run, the observer follows a rather straight-forward path, while in the first example the observer swerve almost immediately in order to reduce the escape risk.
PhaseZero 