Real-time target tracking of an unpredictable target amid unknown obstacles

• US 6,917,855 B2
• Filed: 05/12/2003
• Issued: 07/12/2005
• Est. Priority Date: 05/10/2002
• Status: Expired due to Term

• Current Assignee: Honda Motor Co., Ltd. (Honda Motor Company), Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Honda Motor Co., Ltd. (Honda Motor Company), Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: Lee, Cheng-Yu, Latombe, Jean-Claude, Gonzalez-Banos, Hector
• Primary Examiner(s): Chin, Gary
• Assistant Examiner(s): Marc, McDieunel, Marc, McDieunel
• Application Number:
  US10/435,934
• Publication Number:
  US 20040073368A1
• Time in Patent Office: 792 Days
• Field of Search: 700/245, 700/45, 700/254, 700/63, 700/262, 700/255, 700/259, 318/568.11, 318/568.13, 901/9, 901/48, 901/15, 701/207, 701/301
• US Class Current: 700/245
• CPC Class Codes: G05D 1/0094 involving pointing a payload, e.g. camera, weapon, sensor, towards a fixed or moving target
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/12 Target-seeking control

Abstract

Embodiments provide a strategy for computing the motions of a mobile robot operating in an obstacle-laden environment without requiring prior knowledge of the distribution of obstacles in the environment or knowing the trajectory of a target tracked by the robot. Embodiments provide an algorithm that governs the motion of the observer robot based on measurements of the target'"'"'s position and the location of obstacles in the environment. The algorithm computes a description of the geometric arrangement between the target and the observer'"'"'s visibility region produced by the obstacles and computes a continuous control rule using this description. Embodiments employ an escape-path tree data structure to categorize the target'"'"'s possible modes of escaping from the observer robot'"'"'s sensors and use the escape-path tree to determine the target'"'"'s shortest escape path.

Claims

1. A method for tracking a target moving among a plurality of obstacles in a workspace, comprising:

preparing a visibility region that identifies locations of obstacles from the plurality of obstacles and identifies a location of the target using data received from a sensor;

calculating a plurality of escape paths for the target using the visibility region, each escape path representing a route that would occlude the target from detection by the sensor;

identifying an escape path set from among the plurality of escape paths such that the escape path set represents routes of shortest length from among the plurality of escape paths; and

calculating an escape risk and an escape risk gradient for the escape path set.

2. The method of claim 1, further comprising:

preparing a motion command using the escape risk gradient for an observer robot following the target.

3. The method of claim 2 wherein preparing the motion command further comprises:

calculating a recursive average of the escape risk gradient.

4. The method of claim 1 wherein calculating a plurality of escape paths further comprises:

identifying occlusion regions created by obstacles of the plurality of obstacles, an occlusion region comprising an area in which the sensor cannot detect the target.

5. The method of claim 1 wherein calculating a plurality of escape paths for the target using the visibility region further comprises applying a computer-implemented ray-sweep algorithm to identify the escape paths.

6. A method for tracking a target in a workspace, comprising:

sensing the workspace to obtain a visibility region that identifies the target and at least one obstacle;

calculating an escape risk gradient using the visibility region that a trajectory of the target will escape detection from an observer robot, escape from the observer robot including movement outside the visibility region and movement into an occlusion produced by the at least one obstacle; and

composing a steering command for the observer robot using the escape risk gradient, the steering command reducing the target'"'"'s ability to escape detection from the observer robot.

7. The method of claim 6 wherein calculating the escape risk, further comprises minimizing the escape risk by calculating a reactive term to compensate for the trajectory of the target with respect to a plurality of escape paths and calculating a look-ahead term that compensates for distance between the observer robot and the at least one obstacle.

8. The method of claim 6 wherein the escape risk calculation for each free edge in the visibility region is performed by executing a formula:

φ

^e=cr_o²ƒ

(1/h),

where c is a positive constant, h is a shortest distance between the target and an occlusion between the observer robot and the target, r_o is the distance from the observer robot to an obstacle that could cause an occlusion, and ƒ

(1/h) is a monotonically increasing function of 1/h.

9. The method of claim 6, further comprising:

calculating a plurality of escape risks for the visibility region; and

calculating an escape risk gradient for the plurality of escape risks.

10. The method of claim 9 wherein composing the steering command for the observer robot using the escape risk comprises:

calculating a recursive average of the escape risk gradient.

11. A method for tracking a target moving in a workspace, comprising:

preparing an escape-path tree having the target as a head node;

identifying a plurality of escape paths for the target, each escape path representing a route through the workspace that would occlude the target from at least one sensor;

placing each escape path of the plurality of escape paths as a child node in the escape-path tree, ordering each escape path in the escape-path tree such that escape paths having shorter lengths reside higher in the escape-path tree than escape paths having longer lengths;

selecting a set of escape paths having shorter lengths from the escape-path tree; and

calculating an escape risk for the target using the set of escape paths.

12. The method of claim 11 wherein identifying the plurality of escape paths for the target further comprises applying a computer-implemented ray-sweep algorithm to identify the escape paths.

13. The method of claim 11 wherein calculating the escape risk calculation for every free edge e in the visibility region comprises executing a formula:

φ

^e=cr_o²ƒ

(1/h),

where c is a positive constant, h is a shortest distance between the target and an occlusion between the observer robot and the target, r_o is the distance from the observer robot to an obstacle that could cause an occlusion, and ƒ

(1/h) is a monotonically increasing function of 1/h.

14. The method of claim 11, further comprising:

calculating a plurality of escape risks; and

calculating an escape risk gradient for the plurality of escape risks.

15. The method of claim 14, further comprising:

preparing a motion command using the escape risk gradient for an observer robot following the target.

16. A system for tracking a target moving among a plurality of obstacles in a workspace, comprising:

a visibility acquisition module configured to prepare a visibility region that identifies locations of obstacles from the plurality of obstacles using data received from a sensor;

a target acquisition module configured to locate the target in the visibility region;

an escape-path tree building module configured to identify a plurality of escape paths for the target using the visibility region, each escape path representing a route that would occlude the target from detection by the sensor;

a shortest escape-path tree calculation module configured to identify an escape path set from among the plurality of escape paths such that the escape path set represents routes of shortest length from among the plurality of escape paths; and

a risk gradient calculation module configured to calculate an escape risk gradient for the escape path set.

17. The system of claim 16, further comprising:

a motion command calculation module configured to compose a steering command for the observer robot using the escape risk gradient, the steering command reducing the target'"'"'s ability to escape detection from the sensor.

18. The system of claim 16 wherein the risk gradient calculation module is configured to calculate the escape risk gradient for the escape path set by executing an operation over a risk function associated to every edge e in the visibility region, the operation being given by:

−

∇

φ

^e=2cr_oƒ

(1/h)+c(r_o/h)²ƒ

′

(1/h)∇

h,

where ƒ

′

(1/h) is the mathematical derivative of ƒ

(1/h), and ∇

h—

the gradient of h—

is calculated according to the geometry of the escape path SEP(e, q^t) associated to the edge e. In the above equation, c is a positive constant, h is the shortest distance between the target and an occlusion between the target and an observer robot tracking the target, and r_o is the distance from the observer robot to an obstacle that could cause the occlusion.

19. The system of claim 16 wherein the escape-path tree building module identifies the plurality of escape paths for the target by executing a computer-implemented ray-sweep algorithm.

20. A system for tracking a target in a workspace, comprising:

a sensor configured to obtain data that describes the workspace;

a visibility region acquisition module configured to use data received from the sensor to produce a visibility region that identifies a plurality of obstacles in the workspace;

a target acquisition module configured to identify the target in the workspace;

a risk association module configured to use the visibility region to determine an escape risk that the target will escape detection from an observer robot, escape from the observer robot including target movement outside the visibility region and target movement into an occlusion produced by at least one obstacle of the plurality of obstacles; and

a motion command calculation module configured to compose a steering command for the observer robot using the escape risk, the steering command reducing the target'"'"'s ability to escape detection from the observer robot.

21. The system of claim 20, further comprising:

a risk gradient calculation module configured to calculate an escape risk gradient using the escape risk determined by the risk association module and provide the escape risk gradient to the motion command calculation module for preparation of the steering command.

22. The system of claim 21 wherein the risk gradient calculation module is configured to calculate the escape risk gradient by executing an operation over a risk function associated to every edge e in the visibility region, the operation being given by:

−

∇

φ

^e=2cr_oƒ

′

(1/h)+c(r_o/h)²ƒ

′

(1/h)∇

h,

where ƒ

(1/h) is the mathematical derivative of ƒ

(1/h), and ∇

h—

the gradient of h—

is calculated according to the geometry of the escape path SEP(e, q^t) associated to the edge e. In the above equation, c is a positive constant, h is the shortest distance between the target and an occlusion between the target and an observer robot tracking the target, and r_o is the distance from the observer robot to an obstacle that could cause the occlusion.

23. The system of claim 20 wherein the observer robot is attached to the sensor.

24. The system of claim 20 wherein the observer robot is an anthropomorphic robot and the motion command calculation module prepares the steering command for execution by anthropomorphic actuators.

25. The system of claim 20 wherein the target is a mammal and the sensor is configured to acquire heat-related data that describes the workplace.

26. A system for tracking a target moving in a workspace, comprising:

an escape-path tree building module configured to prepare an escape-path tree having the target as a head node;

identify a plurality of escape paths for the target, each escape path representing a route through the workspace that would occlude the target from at least one sensor;

place each escape path of the plurality of escape paths as a child node in the escape-path tree, order each escape path in the escape-path tree such that escape paths having shorter lengths reside higher in the escape-path tree than escape paths having longer lengths;

a shortest escape-path tree calculation module configured to select a set of escape paths having shorter lengths from the escape-path tree; and

a risk association module configured to calculate an escape risk for the target using the set of escape paths.

27. The system of claim 26, further comprising:

a data repository configured to retain the escape-path tree.