Real-time target tracking of an unpredictable target amid unknown obstacles
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
27 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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. - View Dependent Claims (7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19)
-
-
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. - View Dependent Claims (21, 22, 23, 24, 25)
-
-
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. - View Dependent Claims (27)
-
Specification