Method and apparatus for controlling the movement of a plurality of agents

• US 6,507,771 B2
• Filed: 07/10/2001
• Issued: 01/14/2003
• Est. Priority Date: 07/10/2000
• Status: Expired due to Fees

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Howard, Mike, Lee, Craig, Daily, Mike, Hoff, Bruce, Payton, David W.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Marc, McDieunel, Marc, McDieunel
• Application Number:
  US09/903,879
• Publication Number:
  US 20020138179A1
• Time in Patent Office: 553 Days
• Field of Search: 700/245, 700/250, 700/258, 700/259, 700/249, 700/252, 700/260, 700/261, 700/254, 700/264, 700/246-248, 700/251, 701/200, 701/207, 701/213, 701/217, 701/220, 701/28, 701/23-26, 318/568.1, 318/568.11, 318/568.22, 901/1, 901/9, 901/15, 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 for controlling the movement of agents using local communications is provided. Generally, each agent maintains an optimal distance from other local neighbor agents by, for each agent 200, selecting a local agent 202, measuring the distance and angle to the agent 204, performing a distance maintenance calculation 218, and repeating the distance maintenance calculation 218 for each local agent. In the distance maintenance calculation 218, an attraction/repulsion map is used in order to determine whether an agent is attracted to or repelled from other agents. A motion vector is used to determine agent responses to the attraction or repulsion. Over time, the agents settle into a neutral configuration where each is optimally distanced from the other agents. Reference agents and leader agents can be designated to direct the movement of other agents, and agents can be designated as blocking beacons to repel other agents from undesirable areas.

Claims

1. A method for controlling the movement of a plurality of agents wherein each of one of the plurality of agents has at least one other agent locally spaced at a distance therefrom, and wherein each one of the plurality of agents comprises a means for providing mobility, a means for detecting distance and direction to the at least one other locally spaced agent, a processor coupled with the means for providing mobility and the means for detecting distance and direction in order to control the movement of the agent and to process the distances and directions between the agent and the at least one other locally spaced agent, the method comprising the steps of:

a. determining the distance and direction of each agent from each other agent locally spaced with respect thereto;

b. processing the distances and directions between the agent and each other locally spaced agent; and

c. using a distance-maintenance movement behavior based on the distances and directions between the agent and each other locally spaced agent to maintain a predetermined distance from each other locally spaced agent.

2. A method for controlling the movement of a plurality of agents as set forth in claim 1, wherein the method comprises the further steps of:

i. designating at least one of the plurality of agents to act as a blocking beacon;

ii. preventing movement of the agent designated to act as a blocking beacon; and

iii. urging agents locally spaced with respect to the agent designated to act as a blocking beacon to move away from it, whereby the agent designated as a blocking beacon acts to repel other agents from its vicinity.

3. A method for controlling the movement of a plurality of agents as set forth in claim 1, wherein the step of processing the distances between the agent and each other locally spaced agent is performed by:

i. providing an attraction/repulsion map for each agent, including an attraction region and a repulsion region;

ii. for each other locally spaced agent, determining, based on the attraction/repulsion map, whether the other locally spaced agent is in the attraction region or the repulsion region with respect to the agent;

iii. for each other locally spaced agent in the attraction region of the agent, generating a vector representing attraction of the agent toward the locally spaced agent;

iv. for each other locally spaced agent in the repulsion region of the agent, generating a vector representing the repulsion of the agent from the locally spaced agent;

v. using all of the vectors developed for all of the locally spaced agents to generate a movement vector; and

vi. moving the agent according to the movement vector;

whereby the movement vector is used provide a heading and velocity for the agent in order to perform the step of using a distance-maintenance movement behavior to maintain a predetermined distance from the agent to each other locally spaced agent.

4. A method for controlling the movement of a plurality of agents as set forth in claim 3, wherein the step of processing the distances between the agent and each other locally spaced agent is further performed by:

i. further providing a neutral region to the attraction/repulsion map for each agent; and

ii. for each locally spaced agent, where the agent is in the neutral region of a locally spaced agent, generating a vector representing neutrality toward the locally spaced agent.

5. A method for controlling the movement of a plurality of agents as set forth in claim 4, wherein the step of providing an attraction/repulsion map further comprises the sub-step of configuring the attraction region, the neutral region, and the repulsion region as generally concentric rings around an agent, with the repulsion region residing closest to the agent, the attraction region residing furthest from the agent, and the neutral region residing between the repulsion region and the attraction region, whereby the attraction region and repulsion regions cause movement toward or from an agent and the neutral region causes no movement toward or from an agent, such that the each one of the plurality of agents acts to maintain a predetermined distance from each other agent locally spaced therefrom.

6. A method for controlling the movement of a plurality of agents as set forth in claim 5, wherein the step of providing an attraction/repulsion map further comprises the sub-step of configuring the attraction region with an attraction strength and the repulsion region with a repulsion strength, and wherein the attraction strength and the repulsion strength are functions of the distance from the agent, and wherein the attraction strength is used in generating the vector representing attraction of the agent to the locally spaced agent, and wherein the repulsion strength is used in generating the vector representing repulsion of the agent from the locally spaced agent.

7. A method for controlling the movement of a plurality of agents as set forth in claim 3, wherein the agents are disbursed in an area, and wherein the step of using a distance-maintenance movement behavior further comprises:

a. designating one of the plurality of agents as a leader; and

b. adjusting the attraction/repulsion map the leader such that the leader moves further away from the locally spaced agents with the locally spaced agents urged toward the leader, whereby the leader moves away from the other agents and the other agents follow the leader.

8. A method for controlling the movement of a plurality of agents as set forth in claim 7, wherein the leader designating step is triggered when the number of agents provided is insufficient to fill the area while maintaining the predetermined distance from each other.

9. A method for controlling the movement of a plurality of agents as set forth in claim 7, wherein the leader designating step is triggered explicitly by a user command.

10. A method for controlling the movement of a plurality of agents as set forth in claim 7, wherein the specific agent to serve as the leader is determined by a step selected from the group consisting of (a) selecting the leader explicitly by a user command, (b) selecting a leader through a random selection process, (c) selecting a leader through a repeated random selection process, and (d) selecting the leader through a biased random selection.

11. A method for controlling the movement of a plurality of agents as set forth in claim 10, wherein the leader designating step is periodically repeated upon a triggering event to designate a new leader.

12. A method for controlling the movement of a plurality of agents as set forth in claim 11, wherein the leader designating step further includes the sub-step of transmitting, from the leader, a suppression signal for preventing the repetition of the leader designating step until the occurrence of a triggering event.

13. A method for controlling the movement of a plurality of agents as set forth in claim 12, wherein the suppression signal transmitted from the leader is relayed away from the leader such that it indicates the approximate distance from the leader and such that upon cessation of the transmission of the suppression signal, the random selection process is caused to resume, but is biased in favor of those agents furthest from the leader.

14. A method for controlling the movement of a plurality of agents as set forth in claim 12, wherein the suppression signal transmitted from the leader is relayed away from the leader such that it indicates the approximate distance from the leader and is ineffective for preventing the repetition of the leader designating step at a sufficient distance.

15. A method for controlling the movement of a plurality of agents as set forth in claim 3, further comprising the steps of designating at least one agent as a reference agent with each reference agent transmitting a unique reference signal that is relayed through the plurality of agents in such a way as to provide a distance estimate from the respective reference agent, wherein at least a portion of the other agents respond to the at least one reference signal by moving in a manner determined as a function of the distance estimates of the reference signals.

16. A method for controlling the movement of a plurality of agents as set forth in claim 15, wherein in the reference agent designating step, two agents are designated as reference agents, each transmitting a unique reference signal that is relayed through the plurality of agents in such a way as to provide a distance estimate from the respective reference agent, wherein at least a portion of the other agents respond to the at least one reference signal by moving so as to maintain equality between the distance estimates of the two reference signals.

17. A plurality of controlled-movement agents comprising a plurality of agents, each having at least one other agent locally spaced at a distance therefrom, each one of the plurality of agents including a means for providing mobility, a means for detecting distance and direction to the at least one other locally spaced agent, a processor coupled with the means for providing mobility and the means for detecting distance and direction in order to control the movement of the agent and to process the distances and directions between the agent and the at least one other locally spaced agent, and wherein each agent is operative to determine the distance and direction of each other agent locally spaced with respect thereto, to process the distances and directions between the agent and each other locally spaced agent;

and to maintain a predetermined distance from each other locally spaced agent.

18. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 17, wherein the plurality of agents is further operative to designate one of the plurality of agents to act as a blocking beacon;

to prevent movement of the agent designated to act as a blocking beacon; and

to urge agents locally spaced with respect to the agent designated to act as a blocking beacon to move away from it, whereby the agent designated as a blocking beacon acts to repel other agents from its vicinity.

19. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 17, wherein for the determination of the distances between the agent and each other locally spaced agent, each agent further includes an attraction/repulsion map for each agent, including an attraction region and a repulsion region, where each agent is operative, for each other locally spaced agent, to determine, based on the attraction/repulsion map, whether the agent is in the attraction region or the repulsion region with respect to the other locally spaced agent;

for each other locally spaced agent, where the agent is in the attraction region of a locally spaced agent, the agent is operative to generate a vector representing attraction of the agent toward the locally spaced agent;

for each other locally spaced agent, where the agent is in the repulsion region, the agent is operative to generate a vector representing the repulsion of the agent from the locally spaced agent;

with the agent operative to use all of the vectors developed for all of the locally spaced agents to generate a movement vector; and

wherein the movement vector is used provide a heading and velocity for the agent in order to perform the step of using a distance-maintenance movement behavior to maintain a predetermined distance from the agent to each other locally spaced agent, thereby providing a distance maintenance movement behavior.

20. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 19, wherein the attraction/repulsion maps for each agent include a neutral region, which each locally spaced agent, where the agent is in the neutral region of a locally spaced agent, results in the generation a vector representing neutrality toward the locally spaced agent.

21. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 20, wherein the attraction region, the neutral region, and the repulsion region of the attraction/repulsion map are formed as generally concentric rings around an agent, with the repulsion region residing closest to the agent, the attraction region residing furthest from the agent, and the neutral region residing between the repulsion region and the attraction region, whereby the attraction region and repulsion regions cause movement toward or from an agent and the neutral region causes no movement toward or from an agent, such that the each one of the plurality of agents maintains a predetermined distance from each other agent locally spaced therefrom.

22. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 21, wherein in the attraction/repulsion map the attraction region is configured with an attraction strength and the repulsion region is configured with a repulsion strength, and wherein the attraction strength and the repulsion strength are functions of the distance from the agent, and wherein the attraction strength is used to generate the vector representing attraction of the agent to the locally spaced agent, and wherein the repulsion strength is used to generate the vector representing repulsion of the agent from the locally spaced agent.

23. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 19, wherein one of the plurality of agents is designated as a leader, and wherein the attraction/repulsion map of the leader is adjusted such that the leader moves further away from the locally spaced agents with the locally spaced agents urged toward the leader, whereby the leader moves away from the other agents and the other agents follow the leader.

24. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 23, wherein the designation of the leader is triggered when the number of agents provided is insufficient to fill the area while maintaining the predetermined distance from each other.

25. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 23, wherein the designation of the leader is triggered explicitly by a user command.

26. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 23, wherein the leader is designated in a manner selected from the group consisting of (a) explicitly by a user command, (b) through a random selection process, (c) through a repeated random selection process, and (d) through a biased random selection.

27. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 26, wherein the leader is periodically re-designated upon a triggering event to designate a new leader.

28. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 27, wherein the leader transmits a suppression signal for preventing the re-designating of the leader until the occurrence of a triggering event.

29. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 28, wherein the suppression signal transmitted from the leader is relayed away from the leader such that it indicates the approximate distance from the leader and such that upon cessation of the transmission of the suppression signal, the random selection process is caused to resume, but is biased in favor of those agents furthest from the leader.

30. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 28, wherein the suppression signal transmitted from the leader is relayed away from the leader such that it indicates the approximate distance from the leader and is ineffective for preventing the re-designating of the leader at a sufficient distance.

31. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 19, wherein at least one agent is designated as a reference agent with each reference agent transmitting a unique reference signal that is relayed through the plurality of agents in such a way as to provide a distance estimate from the respective reference agent, wherein at least a portion of the other agents respond to the at least one reference signal by moving in a manner determined as a function of the distance estimates of the reference signals.

32. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 31, wherein two agents are designated as reference agents, each transmitting a unique reference signal that is relayed through the plurality of agents in such a way as to provide a distance estimate from the respective reference agent, wherein at least a portion of the other agents respond to the at least one reference signal by moving so as to maintain equality between the distance estimates of the two reference signals.

33. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 31, wherein two agents are designated as reference agents, each transmitting a unique reference signal that is relayed through the plurality of agents in such a way as to provide a distance estimate from the respective reference agent, wherein at least a portion of the other agents respond to the at least one reference signal by moving so as to maintain equality between the distance estimates of the two reference signals.

34. A plurality of controlled-movement agents comprising a plurality of agents as set forth in claim 19, wherein at least one agent is designated as a reference agent with each reference agent transmitting a unique reference signal that is relayed through the plurality of agents in such a way as to provide a distance estimate from the respective reference agent, wherein at least a portion of the other agents respond to the at least one reference signal by moving in a manner determined as a function of the distance estimates of the reference signals.

35. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent, the controlled movement agent comprising:

a means for providing mobility, a means for detecting distance and direction to the at least one other locally spaced agent, a processor coupled with the means for providing mobility and the means for detecting distance and direction in order to control the movement of the agent and to process the distances and directions between the agent and the at least one other locally spaced agent, and wherein the agent is operative to determine the distance and direction of each other agent locally spaced with respect thereto, to process the distances and directions between the agent and each other locally spaced agent; and

to maintain a predetermined distance from each other locally spaced agent.

36. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 35, wherein the agent may be designated as a blocking beacon, wherein the agent ceases movement and urges agents locally spaced to move away from it, whereby the agent designated as a blocking beacon acts to repel other agents from its vicinity.

37. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 35, wherein for the determination of the distances between the agent and each other locally spaced agent, the agent further includes an attraction/repulsion map for each agent, including an attraction region and a repulsion region, where the agent is operative, for each other locally spaced agent, to determine, based on the attraction/repulsion map, whether the agent is in the attraction region or the repulsion region with respect to the other locally spaced agent;

for each other locally spaced agent, where the agent is in the attraction region of a locally spaced agent, the agent is operative to generate a vector representing attraction of the agent toward the locally spaced agent;

for each other locally spaced agent, where the agent is in the repulsion region, the agent is operative to generate a vector representing the repulsion of the agent from the locally spaced agent;

with the agent operative to use all of the vectors developed for all of the locally spaced agents to generate a movement vector; and

wherein the movement vector is used provide a heading and velocity for the agent in order to perform the step of using a distance-maintenance movement behavior to maintain a predetermined distance from the agent to each other locally spaced agent, thereby providing a distance maintenance movement behavior.

38. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 37, wherein the attraction/repulsion map for the agent includes a neutral region, which, when the agent is in the neutral region of a locally spaced agent, results in the generation a vector representing neutrality toward the locally spaced agent.

39. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 38, wherein the attraction region, the neutral region, and the repulsion region of the attraction/repulsion map are formed as generally concentric rings around an agent, with the repulsion region residing closest to the agent, the attraction region residing furthest from the agent, and the neutral region residing between the repulsion region and the attraction region, whereby the attraction region and repulsion regions cause movement toward or from an agent and the neutral region causes no movement toward or from an agent, such that the the agent maintains a predetermined distance from each other agent locally spaced therefrom.

40. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 39, wherein in the attraction/repulsion map the attraction region is configured with an attraction strength and the repulsion region is configured with a repulsion strength, and wherein the attraction strength and the repulsion strength are functions of the distance from the agent, and wherein the attraction strength is used to generate the vector representing attraction of the agent to the locally spaced agent, and wherein the repulsion strength is used to generate the vector representing repulsion of the agent from the locally spaced agent.

41. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 37, wherein the agent is disbursed in an area and wherein the agent may be designated as a leader, and wherein the attraction/repulsion map of the leader is adjusted such that the leader moves further away from the locally spaced agents with the locally spaced agents urged toward the leader, whereby the leader moves away from the other agents and the other agents follow the leader.

42. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 41, wherein the designation of the leader is triggered when the number of agents provided is insufficient to fill the area while maintaining the predetermined distance from each other.

43. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 41, wherein the designation of the leader is triggered explicitly by a user command.

44. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 41, wherein the leader is designated in a manner selected from the group consisting of (a) explicitly by a user command, (b) through a random selection process, (c) through a repeated random selection process, and (d) through a biased random selection.

45. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 44, wherein the leader is periodically re-designated upon a triggering event to designate a new leader.

46. controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 45, wherein the leader transmits a suppression signal for preventing the re-designating of the leader until the occurrence of a triggering event.

47. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 46, wherein the suppression signal transmitted from the leader is relayed away from the leader such that it indicates the approximate distance from the leader and such that upon cessation of the transmission of the suppression signal, the random selection process is caused to resume, but is biased in favor of those agents furthest from the leader.

48. A controlled-movement agent for use in a plurality of agents including at least one other agent locally spaced at a distance from the controlled-movement agent as set forth in claim 46, wherein the suppression signal transmitted from the leader is relayed away from the leader such that it indicates the approximate distance from the leader and is ineffective for preventing the re-designating of the leader at a sufficient distance.