Method and apparatus for providing agent swarm dispersal and separation by directed movement

• US 6,799,087 B2
• Filed: 01/13/2003
• Issued: 09/28/2004
• Est. Priority Date: 07/10/2000
• Status: Expired due to Fees

• Current Assignee: Fannie Mae, HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Estkowski, Regina
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Marc, McDieunel, Marc, McDieunel
• Application Number:
  US10/342,100
• Publication Number:
  US 20030176947A1
• Time in Patent Office: 624 Days
• Field of Search: 700/245, 700/251, 700/259, 318/568.1, 318/580, 318/587, 701/22, 701/23, 701/28, 701/50, 901/1, 901/3, 901/46, 901/47
• US Class Current: 700/245
• CPC Class Codes: G05D 1/0242 using non-visible light signals, e.g. IR or UV signals
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• CPC Class Codes: G05D 1/0257 using a radar radar systems designed for anti-collision purposes between land vehicles or between land vehicle and fixed obstacles G01S13/931
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0295 by at least one leading vehicle of the fleet
• CPC Class Codes: G08G 1/164 Centralised systems, e.g. external to vehicles
• CPC Class Codes: G08G 1/207 with respect to certain areas, e.g. forbidden or allowed areas with possible alerting when inside or outside boundaries

Abstract

A method, apparatus, and computer program product are presented for directing the movement of an agent in an environment. The operations of the invention comprise determining at least a first zone and direction to objects in at least a portion of the environment around the agent. A determination is also made regarding whether the agent is surrounded by objects. If the agent is surrounded by objects, it stays in the same position, and if it is not surrounded, a determination is made regarding whether the closest object is beyond the first zone from the agent. If the closest object is beyond the first zone, the agent may be moved toward a portion of the environment having the greatest object-saturation, and if the closest object is within the first zone, the agent can be moved toward a portion of the environment having the least object-saturation. Other zones may be provided.

Claims

1. A method for directing movement of an agent in an environment, the method comprising steps of:

determining a first zone within the environment surrounding an agent and directions to any objects in at least a portion of the environment around the agent;

determining whether the agent is surrounded by objects, and if the agent is surrounded by objects, keeping the agent stationary;

if the agent is not surrounded by objects, determining whether a closest object is beyond a first zone from the agent; and

if the closest object is beyond the first zone, moving the agent toward a portion of the environment having a greatest object-saturation; and

if the closest object is within the first zone, moving the agent toward a portion of the environment having a least object-saturation.

2. A method as set forth in claim 1, comprising a further step of, when the closest object is within a second zone, where the second zone is within the first zone, moving the agent toward a portion of the environment having the least object-saturation, and when the closest object is beyond the second zone, but within the first zone, keeping the agent substantially stationary.

3. A method as set forth in claim 1, comprising a further step of, when the closest object is within an immediate zone, where the immediate zone is within a second zone, of performing an adjustment measure with respect to the closest object.

4. A method as set forth in claim 2, comprising a further step of, when the closest object is within an immediate zone, where the immediate zone is within the second zone, of performing an adjustment measure with respect to the closest object.

5. A method as set forth in claim 4, wherein the portion of the environment having the least-object saturation is determined by searching for a minimally populated region outside the second zone having a minimum set of objects.

6. A method as set forth in claim 5, wherein the environment is a physical space, and wherein the minimally populated region is a minimally populated angular region.

7. A method as set forth in claim 6, wherein the minimally populated angular region must exceed a minimum angular value before the agent moves toward the portion of the environment having a least object-saturation.

8. A method as set forth in claim 7, wherein the minimally populated angular region is a maximum unoccupied angular region.

9. A method as set forth in claim 5, wherein the environment is discretized into bins, and wherein the portion of the environment having the least-object saturation is determined by finding the minimally populated bin.

10. A method as set forth in claim 9, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the least-object saturation may be varied.

11. A method as set forth in claim 8, wherein the portion of the environment having a greatest object-saturation is determined by searching for a populated region outside the first zone having a maximum set of objects.

12. A method as set forth in claim 11, wherein the populated region is a maximally populated angular region in a physical space.

13. A method as set forth in claim 12, wherein the maximally populated angular region must be less than a maximum angular value before the agent moves away from the portion of the environment having a greatest object-saturation.

14. A method as set forth in claim 13, wherein the environment is discretized into bins, and wherein the portion of the environment having the greatest-object saturation is determined by finding a maximally populated bin with a maximum set of objects.

15. A method as set forth in claim 14, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the greatest-object saturation may be varied.

16. A method as set forth in claim 13, where the adjustment measure is performed by determining a maximally opposite angular direction from the object within the immediate zone and moving the agent a distance in the maximally opposite direction.

17. A method as set forth in claim 16, where objects are classified into multiple classes, and wherein a first zone, a second zone, and an immediate zone are independently assigned to each class.

18. A method as set forth in claim 17, wherein the first zone, the second zone, and the immediate zone are independently adjustable based on at least one characteristic selected from a group consisting of object class, environmental characteristics, and task characteristics.

19. A method as set forth in claim 18, wherein the classes of objects include other agents and obstacles.

20. A method as set forth in claim 19, wherein the adjustment measure varies according to the class of object in the immediate zone.

21. A method as set forth in claim 20, wherein the agents are mobile computing devices, and wherein the mobile computing devices move within an environment in at least two dimensions.

22. A method as set forth in claim 21, wherein at least one of the minimally populated angular region and the maximally populated angular region are adjusted based on at least one factor selected from a group consisting of object class, environmental characteristics, and task characteristics.

23. A method as set forth in claim 1, wherein the portion of the environment having the least-object saturation is determined by searching for a minimally populated region outside the first zone having a minimum set of objects.

24. A method as set forth in claim 23, wherein the environment is a physical space, and wherein the minimally populated region is a minimally populated angular region.

25. A method as set forth in claim 24, wherein the minimally populated angular region must exceed a minimum angular value before the agent moves toward the portion of the environment having a least object-saturation.

26. A method as set forth in claim 25, wherein the minimally populated angular region is a maximum unoccupied angular region.

27. A method as set forth in claim 26, wherein at least one of the minimally populated angular region and the maximally populated angular region are adjusted based on at least one factor selected from a group consisting of object class, environmental characteristics, and task characteristics.

28. A method as set forth in claim 23, wherein the environment is discretized into bins, and wherein the portion of the environment having the least-object saturation is determined by finding the minimally populated bin.

29. A method as set forth in claim 28, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the least-object saturation may be varied.

30. A method as set forth in claim 1, wherein the portion of the environment having a greatest object-saturation is determined by searching for a populated region outside the first zone having a maximum set of objects.

31. A method as set forth in claim 30, wherein the environment is a physical space, and wherein the populated region is a maximally populated angular region.

32. A method as set forth in claim 31, wherein the maximally populated angular region must be less than a maximum angular value before the agent moves away from the portion of the environment having a greatest object-saturation.

33. A method as set forth in claim 32, wherein at least one of the minimally populated angular region and the maximally populated angular region are adjusted based on at least one factor selected from a group consisting of object class, environmental characteristics, and task characteristics.

34. A method as set forth in claim 30, wherein the environment is discretized into bins, and wherein the portion of the environment having the greatest-object saturation is determined by finding a maximally populated bin with a maximum set of objects.

35. A method as set forth in claim 34, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the greatest-object saturation may be varied.

36. A method as set forth in claim 1, comprising a further step of, when the closest object is within an immediate zone, where the immediate zone is within the first zone, of performing an adjustment measure with respect to the closest object, where the adjustment measure is performed by determining a maximally opposite angular direction from the object within the immediate zone and moving the agent a distance in the maximally opposite direction.

37. A method as set forth in claim 1, where objects are classified into multiple classes, and wherein the first zone is independently assigned to each class.

38. A method as set forth in claim 37, wherein the first zone is adjustable based on at least one characteristic selected from a group consisting of object class, environmental characteristics, and task characteristics.

39. A method as set forth in claim 38, wherein the classes of objects include other agents and obstacles.

40. A method as set forth in claim 1, comprising a further step of, when the closest object is within an immediate zone, where the immediate zone is within the first zone, of performing an adjustment measure with respect to the closest object, wherein the adjustment measure varies according to the class of object in the immediate zone.

41. A method as set forth in claim 1, wherein the agents are mobile computing devices, and wherein the mobile computing devices move within an environment in at least two dimensions.

42. A computer program product for directing movement of an agent in an environment, the computer program product comprising means, operable in a computer system of an agent and encoded in a computer readable medium, for:

determining a first zone within the environment surrounding an agent and directions to any objects in at least a portion of the environment around the agent;

determining whether the agent is surrounded by objects, and if the agent is surrounded by objects, keeping the agent stationary;

if the agent is not surrounded by objects, determining whether a closest object is beyond a first zone from the agent; and

if the closest object is beyond the first zone, moving the agent toward a portion of the environment having a greatest object-saturation; and

if the closest object is within the first zone, moving the agent toward a portion of the environment having a least object-saturation.

43. A computer program product as set forth in claim 42, comprising a further means for, when the closest object is within a second zone, where the second zone is within the first zone, moving the agent toward a portion of the environment having the least object-saturation, and, when the closest object is beyond the second zone, but within the first zone, keeping the agent substantially stationary.

44. A computer program product as set forth in claim 42, comprising a further means for, when the closest object is within an immediate zone, where the immediate zone is within the first zone, of performing an adjustment measure with respect to the closest object.

45. A computer program product as set forth in claim 43, comprising a further means for, when the closest object is within an immediate zone, where the immediate zone is within the second zone, of performing an adjustment measure with respect to the closest object.

46. A computer program product as set forth in claim 45, wherein the portion of the environment having the least-object saturation is determined by searching for a minimally populated region outside the second zone having a minimum set of objects.

47. A computer program product as set forth in claim 46, wherein the environment is a physical space, and wherein the minimally populated region is a minimally populated angular region.

48. A computer program product as set forth in claim 47, wherein the minimally populated angular region must exceed a minimum angular value before the agent moves toward the portion of the environment having a least object-saturation.

49. A computer program product as set forth in claim 48, wherein the minimally populated angular region is a maximum unoccupied angular region.

50. A computer program product as set forth in claim 46, wherein the environment is discretized into bins, and wherein the portion of the environment having the least-object saturation is determined by finding the minimally populated bin.

51. A computer program product as set forth in claim 50, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the least-object saturation may be varied.

52. A computer program product as set forth in claim 49, wherein the portion of the environment having a greatest object-saturation is determined by searching for a populated region outside the first zone having a maximum set of objects.

53. A computer program product as set forth in claim 52, wherein the environment is a physical space, and wherein the populated region is a maximally populated angular region.

54. A computer program product as set forth in claim 53, wherein the maximally populated angular region must be less than a maximum angular value before the agent moves away from the portion of the environment having a greatest object-saturation.

55. A computer program product as set forth in claim 54, wherein the environment is discretized into bins, and wherein the portion of the environment having the greatest-object saturation is determined by finding a maximally populated bin with a maximum set of objects.

56. A computer program product as set forth in claim 55, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the greatest-object saturation may be varied.

57. A computer program product as set forth in claim 54, where the adjustment measure is performed by determining a maximally opposite angular direction from the object within the immediate zone and moving the agent a distance in the maximally opposite direction.

58. A computer program product as set forth in claim 57, where objects are classified into multiple classes, and wherein a first zone, a second zone, and an immediate zone are independently assigned to each class.

59. A computer program product as set forth in claim 58, wherein the first zone, the second zone, and the immediate zone are independently adjustable based on at least one characteristic selected from a group consisting of object class, environmental characteristics, and task characteristics.

60. A computer program product as set forth in claim 59, wherein the classes of objects include other agents and obstacles.

61. A computer program product as set forth in claim 60, wherein the adjustment measure varies according to the class of object in the immediate zone.

62. A computer program product as set forth in claim 61, wherein the agents are mobile computing devices, and wherein the mobile computing devices move within an environment in at least two dimensions.

63. A computer program product as set forth in claim 62, wherein at least one of a minimally populated angular region and a maximally populated angular region are adjusted based on at least one factor selected from a group consisting of object class, environmental characteristics, and task characteristics.

64. A computer program product as set forth in claim 42, wherein the portion of the environment having the least-object saturation is determined by searching for a minimally populated region outside the first zone having a minimum set of objects.

65. A computer program product as set forth in claim 64, wherein the environment is a physical space, and wherein the minimally populated region is a minimally populated angular region.

66. A computer program product as set forth in claim 65, wherein the minimally populated angular region must exceed a minimum angular value before the agent moves toward the portion of the environment having a least object-saturation.

67. A computer program product as set forth in claim 66, wherein the minimally populated angular region is a maximum unoccupied angular region.

68. A computer program product as set forth in claim 67, wherein at least one of a minimally populated angular region and a maximally populated angular region are adjusted based on at least one factor selected from a group consisting of object class, environmental characteristics, and task characteristics.

69. A computer program product as set forth in claim 64, wherein the environment is discretized into bins, and wherein the portion of the environment having the least-object saturation is determined by finding the minimally populated bin.

70. A computer program product as set forth in claim 69, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the least-object saturation may be varied.

71. A computer program product as set forth in claim 42, wherein the portion of the environment having a greatest object-saturation is determined by searching for a populated region outside the first zone having a maximum set of objects.

72. A computer program product as set forth in claim 71, wherein the environment is a physical space, and wherein the populated region is a maximally populated angular region.

73. A computer program product as set forth in claim 72, wherein the maximally populated angular region must be less than a maximum angular value before the agent moves away from the portion of the environment having a greatest object-saturation.

74. A computer program product as set forth in claim 73, wherein at least one of a minimally populated angular region and a maximally populated angular region are adjusted based on at least one factor selected from a group consisting of object class, environmental characteristics, and task characteristics.

75. A computer program product as set forth in claim 71, wherein the environment is discretized into bins, and wherein the portion of the environment having the greatest-object saturation is determined by finding a maximally populated bin with a maximum set of objects.

76. A computer program product as set forth in claim 75, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the greatest-object saturation may be varied.

77. A computer program product as set forth in claim 42, comprising a further means for, when the closest object is within an immediate zone, where the immediate zone is within the first zone, of performing an adjustment measure with respect to the closest object, where the adjustment measure is performed by determining a maximally opposite angular direction from the object within the immediate zone and moving the agent a distance in the maximally opposite direction.

78. A computer program product as set forth in claim 42, where objects are classified into multiple classes, and wherein the first zone is independently assigned to each class.

79. A computer program product as set forth in claim 78, wherein the first zone is adjustable based on at least one characteristic selected from a group consisting of object class, environmental characteristics, and task characteristics.

80. A computer program product as set forth in claim 79, wherein the classes of objects include other agents and obstacles.

81. A computer program product as set forth in claim 42, comprising a further means for, when the closest object is within an immediate zone, where the immediate zone is within the second zone, of performing an adjustment measure with respect to the closest object, wherein the adjustment measure varies according to the class of object in the immediate zone.

82. A computer program product as set forth in claim 42, wherein the agents are mobile computing devices, and wherein the mobile computing devices move within an environment in at least two dimensions.

83. A data processing system for directing movement of an agent in an environment, the data processing system comprising a processor, and a memory coupled with the processor, the data processing system further comprising means, operating therein, for:

determining a first zone within the environment surrounding an agent and directions to any objects in at least a portion of the environment around the agent;

determining whether the agent is surrounded by objects, and if the agent is surrounded by objects, keeping the agent stationary;

if the agent is not surrounded by objects, determining whether a closest object is beyond a first zone from the agent; and

if the closest object is beyond the first zone, moving the agent toward a portion of the environment having a greatest object-saturation; and

if the closest object is within the first zone, moving the agent toward a portion of the environment having a least object-saturation.

84. A data processing system as set forth in claim 83, comprising a further means for, when the closest object is within a second zone, where the second zone is within the first zone, moving the agent toward a portion of the environment having the least object-saturation, and when the closest object is beyond the second zone, but within the first zone, keeping the agent substantially stationary.

85. A data processing system as set forth in claim 83, comprising a further means for, when the closest object is within an immediate zone, where the immediate zone is within the first zone, of performing an adjustment measure with respect to the closest object.

86. A data processing system as set forth in claim 84, comprising a further means for, when the closest object is within an immediate zone, where the immediate zone is within the second zone, of performing an adjustment measure with respect to the closest object.

87. A data processing system as set forth in claim 86, wherein the portion of the environment having the least-object saturation is determined by searching for a minimally populated region outside the second zone having a minimum set of objects.

88. A data processing system as set forth in claim 87, wherein the environment is a physical space, and wherein the minimally populated region is a minimally populated angular region.

89. A data processing system as set forth in claim 88, wherein the minimally populated angular region must exceed a minimum angular value before the agent moves toward the portion of the environment having a least object-saturation.

90. A data processing system as set forth in claim 89, wherein the minimally populated angular region is a maximum unoccupied angular region.

91. A data processing system as set forth in claim 87, wherein the environment is discretized into bins, and wherein the portion of the environment having the least-object saturation is determined by finding the minimally populated bin.

92. A data processing system as set forth in claim 91, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the least-object saturation may be varied.

93. A data processing system as set forth in claim 90, wherein the portion of the environment having a greatest object-saturation is determined by searching for a populated region outside the first zone having a maximum set of objects.

94. A data processing system as set forth in claim 93, wherein the environment is a physical space, and wherein the populated region is a maximally populated angular region.

95. A data processing system as set forth in claim 94, wherein the maximally populated angular region must be less than a maximum angular value before the agent moves away from the portion of the environment having a greatest object-saturation.

96. A data processing system as set forth in claim 95, wherein the environment is discretized into bins, and wherein the portion of the environment having the greatest-object saturation is determined by finding a maximally populated bin with a maximum set of objects.

97. A data processing system as set forth in claim 96, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the greatest-object saturation may be varied.

98. A data processing system as set forth in claim 95, where the adjustment measure is performed by determining a maximally opposite angular direction from the object within the immediate zone and moving the agent a distance in the maximally opposite angular direction.

99. A data processing system as set forth in claim 98, where objects are classified into multiple classes, and wherein a first zone, a second zone, and an immediate zone are independently assigned to each class.

100. A data processing system as set forth in claim 99, wherein the first zone, the second zone, and the immediate zone are independently adjustable based on at least one characteristic selected from a group consisting of object class, environmental characteristics, and task characteristics.

101. A data processing system as set forth in claim 100, wherein the classes of objects include other agents and obstacles.

102. A data processing system as set forth in claim 101, wherein the adjustment measure varies according to the class of object in the immediate zone.

103. A data processing system as set forth in claim 102, wherein the agents are mobile computing devices, and wherein the mobile computing devices move within an environment in at least two dimensions.

104. A data processing system as set forth in claim 103, wherein at least one of a minimally populated angular region and a maximally populated angular region are adjusted based on at least one factor selected from a group consisting of object class, environmental characteristics, and task characteristics.

105. A data processing system as set forth in claim 83, wherein the portion of the environment having the least-object saturation is determined by searching for a minimally populated region outside the first zone having a minimum set of objects.

106. A data processing system as set forth in claim 105, wherein the environment is a physical space, and wherein the minimally populated region is a minimally populated angular region.

107. A data processing system as set forth in claim 106, wherein the minimally populated angular region must exceed a minimum angular value before the agent moves toward the portion of the environment having a least object-saturation.

108. A data processing system as set forth in claim 107, wherein the minimally populated angular region is a maximum unoccupied angular region.

109. A data processing system as set forth in claim 108, wherein at least one of a minimally populated angular region and a maximally populated angular region are adjusted based on at least one factor selected from a group consisting of object class, environmental characteristics, and task characteristics.

110. A data processing system as set forth in claim 105, wherein the environment is discretized into bins, and wherein the portion of the environment having the least-object saturation is determined by finding the minimally populated bin.

111. A data processing system as set forth in claim 110, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the least-object saturation may be varied.

112. A data processing system as set forth in claim 83, wherein the portion of the environment having a greatest object-saturation is determined by searching for a populated region outside the first zone having a maximum set of objects.

113. A data processing system as set forth in claim 112, wherein the environment is a physical space, and wherein the populated region is a maximally populated angular region.

114. A data processing system as set forth in claim 113, wherein the maximally populated angular region must be less than a maximum angular value before the agent moves away from the portion of the environment having a greatest object-saturation.

115. A data processing system as set forth in claim 114, wherein at least one of a minimally populated angular region and a maximally populated angular region are adjusted based on at least one factor selected from a group consisting of object class, environmental characteristics, and task characteristics.

116. A data processing system as set forth in claim 112, wherein the environment is discretized into bins, and wherein the portion of the environment having the greatest-object saturation is determined by finding a maximally populated bin with a maximum set of objects.

117. A data processing system as set forth in claim 116, wherein the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the greatest-object saturation may be varied.

118. A data processing system as set forth in claim 83, comprising a further means for, when the closest object is within an immediate zone, where the immediate zone is within the first zone, of performing an adjustment measure with respect to the closest object, where the adjustment measure is performed by determining a maximally opposite angular direction from the object within the immediate zone and moving the agent a distance in the maximally opposite direction.

119. A data processing system as set forth in claim 83, where objects are classified into multiple classes, and wherein the first zone is independently assigned to each class.

120. A data processing system as set forth in claim 119, wherein the first zone is adjustable based on at least one characteristic selected from a group consisting of object class, environmental characteristics, and task characteristics.

121. A data processing system as set forth in claim 120, wherein the classes of objects include other agents and obstacles.

122. A data processing system as set forth in claim 83, comprising a further means for, when the closest object is within an immediate zone, where the immediate zone is within the first zone, of performing an adjustment measure with respect to the closest object, wherein the adjustment measure varies according to the class of object in the immediate zone.

123. A data processing system as set forth in claim 83, wherein the agents are mobile computing devices, and wherein the mobile computing devices move within an environment in at least two dimensions.

124. A data processing system as set forth in claim 83, further comprising at least one sensor coupled with the processor for receiving information selected from a group comprising information regarding objects and information regarding the environment, and at least one means for mobility coupled with and controlled by the processor.

125. A data processing system as set forth in claim 124, further comprising a communication module connected with the processor for communicating with other agents.

126. A data processing system as set forth in claim 125, further comprising an output connected with the processor for providing output data from the data processing system.

127. A data processing system as set forth in claim 126, further comprising an input for receiving information, whereby the data processing system can receive commands from a user, a computer system, or from other agents.

128. A data processing system as set forth in claim 83, wherein operations of the data processing system are centralized.

129. A data processing system as set forth in claim 83, wherein the operations of the data processing system are distributed.