US6917855B2 — Real-time target tracking of an unpredictable tar…

Claim 1

Independent Claim 117 words

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.

Claim 2

Independent Claim 117 words

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.

Claim 3

Dependent Claim 24 words

The method of claim 1 , further comprising: preparing a motion command using the escape risk gradient for an observer robot following the target.

Claim 4

Dependent Claim 21 words

The method of claim 2 wherein preparing the motion command further comprises: calculating a recursive average of the escape risk gradient.

Claim 5

Dependent Claim 39 words

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.

Claim 6

Dependent Claim 31 words

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.

Claim 7

Independent Claim 100 words

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.

Claim 8

Independent Claim 100 words

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.

Claim 9

Dependent Claim 56 words

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.

Claim 10

Dependent Claim 82 words

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 2 ƒ(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.

Claim 11

Dependent Claim 30 words

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.

Claim 12

Dependent Claim 28 words

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.

Claim 13

Independent Claim 122 words

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.

Claim 14

Independent Claim 122 words

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.

Claim 15

Dependent Claim 27 words

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.

Claim 16

Dependent Claim 82 words

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 2 ƒ(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.

Claim 17

Dependent Claim 26 words

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.

Claim 18

Dependent Claim 24 words

The method of claim 14 , further comprising: preparing a motion command using the escape risk gradient for an observer robot following the target.

Claim 19

Independent Claim 147 words

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.

Claim 20

Independent Claim 147 words

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.

Claim 21

Dependent Claim 41 words

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.

Claim 22

Dependent Claim 144 words

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 =2 cr o ƒ(1 /h )+ c ( r o /h ) 2 ƒ′(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.

Claim 23

Dependent Claim 26 words

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.

Claim 24

Independent Claim 147 words

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.

Claim 25

Independent Claim 147 words

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.

Claim 26

Dependent Claim 48 words

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.

Claim 27

Dependent Claim 139 words

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 =2 cr o ƒ′(1 /h )+ c ( r o /h ) 2 ƒ′(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.

Claim 28

Dependent Claim 14 words

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

Claim 29

Dependent Claim 28 words

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.

Claim 30

Dependent Claim 24 words

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.

Claim 31

Independent Claim 143 words

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.

Claim 32

Independent Claim 143 words

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.

Claim 33

Dependent Claim 17 words

The system of claim 26 , further comprising: a data repository configured to retain the escape-path tree.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2008-07-11	2009-01-10	2009-07-12	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2012-07-11	2013-01-10	2013-07-12	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2016-07-11	2017-01-10	2017-07-12	$7700.00	Window Closed / Lapsed

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

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag