System and method for automated search by distributed elements

• US 7,908,040 B2
• Filed: 07/15/2004
• Issued: 03/15/2011
• Est. Priority Date: 07/15/2004
• Status: Expired due to Fees

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Bradshaw, Wendell, Payton, David, Howard, Michael D., Smith, Timothy
• Primary Examiner(s): Tran; Khoi
• Assistant Examiner(s): Amin; Bhavesh V
• Application Number:
  US10/892,747
• Publication Number:
  US 20060015215A1
• Time in Patent Office: 2,434 Days
• Field of Search: 701/3, 701/207, 703/6, 382/159, 382/228, 318/568.12, 318/568.16, 702/19, 700/245, 700/247, 700/248
• US Class Current: 701/1
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0094 involving pointing a payload, e.g. camera, weapon, sensor, towards a fixed or moving target

Abstract

A system and method for decentralized cooperative control of a team of agents for geographic and other search tasks. The approach is behavior-based and uses probability particle approach to the search problem. Agents are attracted to probability distributions in the form of virtual particles of probability that represent hypotheses about the existence of objects of interest in a geographic area or a data-space. Reliance on dependable, high-bandwidth communication is reduced by modeling the movements of other team members and the objects of interest between periodic update messages.

Claims

1. A search system comprising:

a plurality of sensors for detecting an object of interest;

a predictive model which receives an output from at least one of said plurality of sensors, said predictive model for predicting a behavior of said object using a probability distribution in the form of a set of particles; and

a processor for directing a respective sensor to search a unique area of a search space predicted to include the object by said predictive model.

2. The system of claim 1 wherein the predictive model is adapted to direct at least two sensors using a clustering technique that partitions the particles into one group for each sensor.

3. The system of claim 2 wherein:

the probability distribution of particles which form the set of particles is a cluster; and

each of the at least two sensors is directed to search a respective cluster selected by said predictive model.

4. The system of claim 3 wherein the processor is adapted to direct respective sensors toward a center of mass of said probability distribution of particles.

5. The system of claim 3 wherein said predictive model is adapted to direct each sensor toward a selected one of the particles in the cluster selected by said predictive model.

6. The system of claim 5 wherein each sensor eliminates particles that represent the area of the search space observed by other sensors.

7. The system of claim 5 wherein each of the eliminated particles reappear after a predetermined period of time.

8. The system of claim 5 wherein the predictive model is adapted such that as each sensor obtains more information about an object of interest, the probability distribution of particles related to that object of interest is modified to better represent the new information.

9. The system of claim 1 further including means for receiving updates regarding other sensors.

10. The system of claim 9 further including means for modeling activities of other sensors in time intervals between updates on activities of such other sensors.

11. The system of claim 10 wherein said update includes information regarding current focus of attention of other sensors.

12. The system of claim 11 wherein the current focus of attention is a field of regard of a sensor.

13. The system of claim 1 wherein said behavior is movement in three-dimensional physical space.

34. The system of claim 2, wherein the clustering technique is a K-means clustering technique.

35. The system of claim 34, wherein the K-means clustering technique partitions particles into a number of particle clusters equal to the number of sensors and each sensor is assigned to search one of the particle clusters.

36. The system of claim 35, wherein sensor assignments are based upon a distance between sensor location and particle cluster center of mass.

37. The system of claim 35, wherein each of said plurality of sensors is directed toward a waypoint defined by an assigned particle cluster center of mass.

38. The system of claim 35, wherein at least one of said plurality of sensors is further directed to search a subcluster of particles of an assigned particle cluster.

14. A system for searching for an object of interest, the system comprising:

a plurality of mobile platforms, each of said plurality of mobile platforms including;

a detector mounted on the mobile platform, said detector for detecting the object of interest; and

a processor, mounted on the mobile platform, said processor having a plurality of hypothesized identities of the object of interest and having a like plurality of predictive models, one predictive model for each of the plurality of hypothesized identities, said processor for predicting a behavior of the object of interest using a predictive model and in response to said processor predicting a behavior of the object of interest, said processor directs the platform to the object of interest and wherein;

the predictive model includes a probability distribution in the form of a set of particles;

the predictive model is adapted to receive updates on an identity of the object of interest; and

the predictive model moves particles within the set of particles to reflect the behavior of the object of interest.

15. The system of claim 14 wherein each of the plurality of predictive models are adapted to receive updates on a location of the object of interest.

16. The system of claim 15 wherein the updates contain probabilistic information about the object of interest.

17. The system of claim 14 wherein said detector on each of said plurality of mobile platforms is directed within a search area.

18. The system of claim 17 wherein at least one of said plurality of mobile platforms is a robot.

19. The system of claim 18 wherein all of said plurality of mobile platforms are provided as robots.

20. A search system comprising:

a plurality of mobile platforms, each of said plurality of mobile platforms comprising;

(a) a detector for detecting an object of interest; and

(b) a processor for predicting a behavior of the object of interest using a predictive model and, in response to behavior predicted by said processor, for directing the mobile platform on which said processor is disposed to search a unique area of a search space including the object of interest and wherein the predictive model includes a probability distribution in the form of a set of particles and wherein the predictive model moves particles within the set of particles to reflect the behavior of the object of interest.

21. The system of claim 20 wherein each mobile platform is a robot and the predictive model is adapted to direct each robot using a clustering technique that partitions the particles into one group for each detector.

22. The system of claim 21 wherein said probability distribution of said particles is a cluster.

23. The system of claim 22 wherein each of said robots is directed to search a respective cluster selected by the predictive model.

24. The system of claim 23 wherein the predictive model in each of said plurality robots is adapted to direct the detector of each robot toward a selected one of the particles in the cluster selected by the predictive model.

25. The system of claim 24 wherein each robot adjusts the predictive model by eliminating particles that represent an area of the search space observed by its detector and the detector of other robots.

26. The system of claim 25 wherein the predictive model is updated after a predetermined period of time by adding back at least some eliminated particles.

27. The system of claim 24 wherein the predictive model is adapted such that as each robot obtains more information about an object of interest, at least one of:

a distribution of particles related to the object of interest is modified to better represent the new information;

or

a density of particles related to the object of interest is modified to better represent the new information.

28. The system of claim 20 further comprising:

(c) means for tracking the object of interest using the set of particles.

29. The system of claim 20 further comprising:

(c) means for receiving updates regarding other mobile platforms.

30. The system of claim 29 further including means for modeling activities of other mobile platforms in time intervals between updates on activities of such other mobile platforms.

31. The system of claim 30 wherein said update includes information regarding current focus of attention of other mobile platforms.

32. The system of claim 31 wherein the current focus of attention is a field of regard of the detector of a mobile platform.

33. The system of claim 20 wherein said behavior is movement in three-dimensional physical space.

39. The system of claim 20 wherein the predictive model is a first one of a plurality of predictive models with each of the plurality of predictive models corresponding to one of a plurality of hypothesized identifies of the object of interest.

40. The system of claim 20 wherein the predictive model is adapted to receive updates on an identity of the object of interest.