Method and system for tracking moving objects

• US 6,801,850 B1
• Filed: 10/29/2001
• Issued: 10/05/2004
• Est. Priority Date: 10/30/2000
• Status: Expired due to Term

• Current Assignee: Fluensee Incorporated (TrackX Holdings, Inc.)
• Original Assignee: University of Illinois
• Inventors: Wolfson, Ouri
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US10/040,221
• Time in Patent Office: 1,072 Days
• Field of Search: 701/209, 701/201, 701/202, 701/204, 701/205, 701/210, 701/211, 701/203, 340/988, 340/990, 340/991, 340/992, 340/993, 340/995.23, 340/995
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G08G 1/20 Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A database receives location information about a moving object. Using the destination of the object and an electronic map, the database finds a projected path for the moving object. From the projected path, the database computes a trajectory. The trajectory may be used to estimate past and future positions of the moving object. The moving object may send location updates to the database when its actual location differs from its anticipated location by more than an uncertainty threshold.

Claims

1. A method for creating an uncertainty-based trajectory for a moving object, the method comprising:

obtaining a sequence of expected locations for the moving object including a starting point, a destination point and intermediate points;

computing a temporal-spatial path along which the moving object travels from the starting point through the intermediate points to the destination point; and

constructing a trajectory that encompasses all possible temporal-spatial paths along which the moving object may travel from the starting point through the intermediate points to the destination point within a range of spatial and temporal uncertainties relative to the temporal-spatial path.

2. A computer readable medium having stored therein instructions for causing a processor to execute the method of claim 1.

3. The method of claim 1, further comprising:

receiving an actual location of the moving object;

determining that the actual location of the moving object is within the range of spatial and temporal uncertainties defined by the trajectory; and

continuing to use the trajectory.

4. The method of claim 3, wherein the actual location is received from the moving object.

5. The method of claim 1, further comprising:

receiving an actual location of the moving object;

determining that the actual location of the moving object is not within the range of spatial and temporal uncertainties defined by the trajectory; and

re-constructing the trajectory based on the actual location of the moving object.

6. The method of claim 1, further comprising:

receiving a travel update denoting a change in an anticipated travel time along at least one segment of the temporal-spatial path; and

responsively re-constructing the trajectory.

7. A method for using an uncertainty-based trajectory to monitor a moving object, the method comprising:

obtaining a sequence of expected locations for the moving object including a starting point, a destination point and at least one intermediate point;

computing a temporal-spatial path along which the moving object travels from the starting point through the at least one intermediate point to the destination point; and

constructing a trajectory for the moving object, wherein the trajectory defines permissible spatial and temporal uncertainties in actual locations of a moving object relative to expected locations of the moving object along the temporal-spatial path, and wherein the trajectory is created by projecting a multi-dimensional sphere along an uncertainty bound reduction of the temporal-spatial path.

8. A computer readable medium having stored therein instructions for causing a processor to execute the method of claim 7.

9. The method of claim 7, wherein the multi-dimensional sphere is a 4-dimensional sphere with three spatial dimensions and one temporal dimension, and wherein a radius of the sphere represents a permissible uncertainty.

10. The method of claim 7, wherein the multi-dimensional sphere is a 3-dimensional sphere with three spatial dimensions, and wherein a radius of the sphere represents a permissible uncertainty.

11. The method of claim 7, further comprising:

receiving an actual location of the moving object; and

determining that the actual location of the moving object is not within the range of spatial and temporal uncertainties defined by the trajectory; and

re-constructing the trajectory based on the actual location of the moving object.

12. A method for constructing an uncertainty-based trajectory for a moving object, the method comprising:

obtaining a sequence of expected locations for the moving object including a starting point, a destination point and intermediate points;

computing a temporal-spatial path along which the moving object travels from the starting point through the intermediate points to the destination point; and

constructing a trajectory for the moving object, wherein the trajectory defines permissible temporal and spatial deviations of actual locations of the moving object relative to expected locations of the moving object on the temporal-spatial path.

13. A computer readable medium having stored therein instructions for causing a processor to execute the method of claim 12.

14. The method of claim 12, further comprising:

receiving an actual location of the moving object;

determining whether the actual location of the moving object is within the range of spatial and temporal uncertainties defined by the trajectory; and

if the actual location of the moving object is within the range of spatial and temporal uncertainties defined by the trajectory, continuing to use the trajectory.

15. The method of claim 12, further comprising:

receiving an actual location of the moving object;

determining whether the actual location of the moving object is within the range of spatial and temporal uncertainties defined by the trajectory; and

if the actual location of the moving object is not within the range of spatial and temporal uncertainties defined by the trajectory, then re-constructing the trajectory based on the actual location of the moving object.

16. A method for implementing an uncertainty-based trajectory for a moving object, the method comprising:

obtaining a sequence of expected locations for the moving object including a starting point, a destination point and intermediate points;

computing a temporal-spatial path along which the moving object travels from the starting point through the intermediate points to the destination point; and

creating a trajectory for the moving object, wherein the trajectory defines permissible spatial and temporal uncertainties in a given actual location of the moving object relative to an expected location along the temporal-spatial path.

17. A computer readable medium having stored therein instructions for causing a processor to execute the method of claim 16.

18. The method of claim 16, wherein creating the trajectory comprises projecting a 4-dimensional sphere along an uncertainty bound reduction of the temporal-spatial path, wherein the sphere includes three spatial dimensions and one temporal dimension, and wherein a radius of the sphere represents a permissible uncertainty relative to an expected location of the moving object that corresponds to a center of the sphere.

19. The method of claim 16, further comprising:

receiving an actual location of the moving object; and

responsively re-creating the trajectory based on the actual location of the moving object, the destination point and at least one intermediate point.

20. The method of claim 19, further comprising providing the re-created trajectory to the moving object.

21. A method for a moving object to validate a trajectory, the method comprising:

receiving from a tracking server a trajectory, wherein the trajectory represents all possible temporal-spatial paths along which the moving object may travel from a starting point through intermediate points to a destination point within a range of spatial and temporal uncertainties;

obtaining a first current location of the moving object;

determining that the first current location of the moving object is not within the range of spatial and temporal uncertainties defined by the trajectory; and

responsively reporting the first current location of the moving object to the tracking server.

22. A computer readable medium having stored therein instructions for causing a processor to execute the method of claim 21.

23. The method of claim 21, further comprising receiving from the tracking server a recomputed trajectory in response to reporting the first current location.

24. The method of claim 23, further comprising:

obtaining a second current location of the moving object

determining that the second current location of the moving object is not within the range of spatial and temporal uncertainties defined by the recomputed trajectory; and

responsively reporting the second current location to the tracking server.

25. A method for tracking locations of moving objects, the method comprising:

creating a respective trajectory for each of a plurality of moving objects, wherein each respective trajectory encompasses all possible temporal-spatial paths along which a respective one of the moving objects may travel between starting and destination locations within a range of spatial and temporal uncertainties; and

sending each trajectory to its respective moving object.

26. A computer readable medium having stored therein instructions for causing a processor to execute the method of claim 25.

27. The method of claim 25, further comprising:

receiving from one of the moving objects an actual location of the moving object; and

determining whether the actual location of the moving object is within the range of the spatial and temporal uncertainties defined by the respective trajectory.

28. The method of claim 27, further comprising:

determining that the actual location of the moving object is not within range of the spatial and temporal uncertainties defined by its respective trajectory;

re-creating the respective trajectory based on the actual location; and

sending the re-created trajectory to the moving object.

29. The method of claim 25, further comprising:

displaying each trajectory superimposed over a map;

displaying an expected location for each moving object superimposed over the map; and

periodically displaying updated expected locations for each moving object.

30. The method of claim 25, further comprising:

receiving an actual location of one of the moving objects;

determining that the actual location of the moving object is not within range of the spatial and temporal uncertainties defined by the respective trajectory;

re-creating the respective trajectory based on the actual location; and

displaying the re-created trajectory superimposed over the map.