Method and apparatus for controlling the movement of a plurality of agents
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
48 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
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.
- View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
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. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48)
- 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
Specification