System and method for automated search by distributed elements

• US 20060015215A1
• Filed: 07/15/2004
• Published: 01/19/2006
• Est. Priority Date: 07/15/2004
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Bradshaw, Wendell, Payton, David, Howard, Michael D., Smith, Timothy
• Granted Patent: US 7,908,040 B2
• Time in Patent Office: Days
• US Class Current: 700/245
• 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:

first means for detecting an object of interest;

second means for predicting a behavior of said object; and

third means for directing said first means to said object in response to said means for predicting behavior.

2. The invention of claim 1 wherein said first, second and third means are disposed within a mobile platform.

3. The invention of claim 2 wherein said mobile platform is a robot.

4. The invention of claim 3 wherein said mobile platform is an unmanned vehicle.

5. The invention of claim 1 wherein said means for predicting behavior includes a predictive model.

6. The invention of claim 5 wherein said model includes a probability distribution in the form of a set of particles.

7. The invention of claim 6 wherein said second means includes means for moving said particles to reflect the behavior of said object.

8. The invention of claim 7 wherein said second means includes plural models, one for each hypothesized identity of said object.

9. The invention of claim 8 further including means for receiving updates on a location of said object.

10. The invention of claim 9 further including means for receiving updates on an identity of said object.

11. The invention of claim 10 wherein said updates contain probabilistic information about said object.

12. The invention of claim 11 wherein a frequency or availability of said updates is uncertain.

13. The invention of claim 6 wherein said first means is directed within a search area.

14. The invention of claim 13 wherein said first, second and third means are disposed within a mobile platform.

15. The invention of claim 14 wherein said platform is a robot.

16. The invention of claim 15 wherein said system includes plural robots.

17. The invention of claim 16 wherein said model is adapted to direct each robot to search a unique area of said search space.

18. The invention of claim 17 wherein said model is adapted to direct each robot to search a unique area of said search space using probability distributions in the form of particles.

19. The invention of claim 18 wherein the model is adapted to direct each robot to search a unique area of said search space using a clustering technique that partitions the particles into one group for each searcher.

20. The invention of claim 18 wherein the model is adapted to assign robots to groups of particles in a unique manner.

21. The invention of claim 18 wherein the model is adapted to assign robots to groups of particles in a manner computed by each robot using predetermined properties of the robots.

22. The invention of claim 19 wherein the clustering technique is K-Means.

23. The invention of claim 19 wherein said probability distribution of said particles is a cluster.

24. The invention of claim 23 wherein each of said robots is directed to search a respective cluster selected by said model.

25. The invention of claim 24 wherein each third means of each robot is adapted to direct said first means thereof toward a center of mass of said probability distribution of particles.

26. The invention of claim 24 wherein said model is adapted to direct the detector of each robot toward a selected one of the particles in the cluster selected by said model.

27. The invention of claim 26 wherein each robot eliminates particles that represent the area of the search space observed by its sensor and that of other searchers.

28. The invention of claim 26 wherein each of the eliminated particles reappear after a predetermined period of time.

29. The invention of claim 26 wherein the model is adapted such that as each robot obtains more information about an object of interest, a distribution or density of particles related to that object of interest are modified to better represent the new information.

30. The invention of claim 18 including means for tracking said object using said particles.

31. The invention of claim 16 further including means for receiving updates regarding other robots.

32. The invention of claim 31 further including means for modeling activities of other searchers in time intervals between updates on activities of such other searchers.

33. The invention of claim 32 wherein said update includes information regarding location of other searchers.

34. The invention of claim 32 wherein said update includes information regarding current focus of attention of other searchers.

35. The invention of claim 34 wherein the current focus of attention is a field of regard of a physical sensor of a searcher.

36. The invention of claim 32 wherein said update includes information regarding prior focus of attention of other searchers.

37. The invention of claim 32 wherein said update includes information regarding velocity of other searchers.

38. The invention of claim 32 wherein said update includes information regarding future movement of other searchers.

39. The invention of claim 32 wherein said update includes information regarding object properties ascertained by other searchers.

40. The invention of claim 1 wherein said behavior is movement in 3D physical space.

41. The invention of claim 1 wherein said behavior involves changing observable properties

42. The invention of claim 1 wherein said behavior is movement in a non-physical data space.

43. A search system comprising:

a plurality of mobile platforms;

a detector mounted on each platform for detecting an object of interest; and

a processor mounted on each platform for predicting a behavior of said object and for directing a respective platform to said object in response to predicted behavior.

44. The invention of claim 43 wherein said processor executes software including a predictive model.

45. The invention of claim 44 wherein said model includes a probability distribution in the form of a set of particles.

46. The invention of claim 45 wherein said model moves said particles to reflect the behavior of said object.

47. The invention of claim 46 wherein said model includes plural models, one for each hypothesized identity of said object.

48. The invention of claim 47 wherein said model is adapted to receive updates on a location of said object.

49. The invention of claim 48 wherein said model is adapted to receive updates on an identity of said object.

50. The invention of claim 49 wherein said updates contain probabilistic information about said object.

51. The invention of claim 50 wherein a frequency or availability of said updates is uncertain.

52. The invention of claim 43 wherein said detector is directed within a search area.

53. The invention of claim 52 wherein said platform is a robot.

54. The invention of claim 53 wherein said system includes plural robots.

55. The invention of claim 54 wherein said model is adapted to direct each robot to search a unique area of said search space.

56. The invention of claim 55 wherein said model is adapted to direct each robot to search a unique area of said search space using probability distributions in the form of particles.

57. The invention of claim 56 wherein the model is adapted to direct each robot to search a unique area of said search space using a clustering technique that partitions the particles into one group for each searcher.

58. The invention of claim 57 wherein the clustering technique is K-Means.

59. The invention of claim 57 wherein the model is adapted to assign robots to groups of particles in a unique manner.

60. The invention of claim 57 wherein the model is adapted to assign robots to groups of particles in a manner computed by each robot using predetermined properties of the robots.

61. The invention of claim 60 wherein said probability distribution of said particles is a cluster.

62. The invention of claim 61 wherein each of said robots is directed to search a respective cluster selected by said model.

63. The invention of claim 62 wherein each third means of each robot is adapted to direct said first means thereof toward a center of mass of said probability distribution of particles.

64. The invention of claim 62 wherein said model is adapted to direct the detector of each robot toward a selected one of the particles in the cluster selected by said model.

65. The invention of claim 64 each robot eliminates particles that represent the area of the search space observed by its sensor and that of other searchers.

66. The invention of claim 64 wherein each of the eliminated particles reappear after a predetermined period of time.

67. The invention of claim 64 wherein the model is adapted such that as each robot obtains more information about an object of interest, a distribution or density of particles related to that object of interest are modified to better represent the new information.

68. The invention of claim 43 including means for tracking said object using said particles.

69. The invention of claim 53 further including means for receiving updates regarding other robots.

70. The invention of claim 69 further including means for modeling activities of other searchers in time intervals between updates on activities of such other searchers.

71. The invention of claim 70 wherein said update includes information regarding location of other searchers.

72. The invention of claim 70 wherein said update includes information regarding current focus of attention of other searchers.

73. The invention of claim 72 wherein the current focus of attention is a field of regard of a physical sensor of a searcher.

74. The invention of claim 70 wherein said update includes information regarding prior focus of attention of other searchers.

75. The invention of claim 74 wherein said update includes information regarding velocity of other searchers.

76. The invention of claim 75 wherein said update includes information regarding future movement of other searchers.

77. The invention of claim 76 wherein said update includes information regarding object properties ascertained by other searchers.

78. The invention of claim 43 wherein said behavior is movement in 3D physical space.

79. The invention of claim 43 wherein said behavior involves changing observable properties

80. The invention of claim 43 wherein said behavior is movement in a non-physical data space.

81. A search method including the steps of:

providing a detector for detecting an object of interest;

processing data from said detector with a model for predicting a behavior of said object; and

directing said detector to said object in response to data output by said model.