Data processing: generic control systems or specific application – Specific application – apparatus or process – Robot control
Reexamination Certificate
2001-07-10
2003-01-14
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Robot control
C700S246000, C700S247000, C700S248000, C700S249000, C700S250000, C700S251000, C700S252000, C700S258000, C700S259000, C700S260000, C700S261000, C700S264000, C701S023000, C701S024000, C701S025000, C701S026000, C701S200000, C701S207000, C701S213000, C701S217000, C701S220000, C318S568100, C318S568110, C318S568220, C901S001000
Reexamination Certificate
active
06507771
ABSTRACT:
TECHNICAL FIELD
The present invention is related to the field of controlling movement for large groups of agents. More specifically, this disclosure presents a method for controlling the movement of a plurality of agents using local, low bandwidth communications.
BACKGROUND
Over the past few decades, approaches to controlling agents have focused on individual agents and a centralized database. As a result, traditional control of agents and sensors has taken the form of a single mobile agent or a small number of agents using a pre-constructed digital map to aid in path planning and control of the agents or agents. It was necessary to develop a large centralized terrain/environment database to serve as the preconstructed digital map for geometric computations. Typical computations at these centralized databases include determination of shortest path to destination, and routes to destinations. Information relevant to these approaches can be found in U.S. Pat. Nos. 4,119,900; 4,882,694; 5,165,064; and 5,170,351. However, the agent control systems disclosed in each one of these references suffers from one or more of the following disadvantages: 1) the agent is oriented within a fixed surface area; 2) the system only allows for narrow applications of distance-maintenance; 3) the system requires a master station and a means to locate agent; 4) the system requires cameras to locate the mobile agents; 5) the employment of an array of ultrasonic transducers is required on mobile agents; 6) each agent is individually controlled and monitored by a large master station database; and 7) each agent monitors a sector of workspace. Thus, it is desirable to provide a method and apparatus for overcoming these limitations.
SUMMARY OF THE PRESENT INVENTION
The present invention provides a method and apparatus for controlling the movement of a plurality of agents. Specifically, the present invention provides the control mechanism through the use of a signaling mechanism wherein certain criteria of a signal, either explicit (such as information embedded in a signal) or implicit (such as an inherent property of the signal like the transmission power) in order to set up ranges of attraction and repulsion in order to maintain a predetermined distance between the agents.
The present invention provides 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. 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, and a processor coupled with the means for providing mobility and with 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.
In one embodiment, the method comprises the steps of determining the distance and direction of each agent from each other agent locally spaced with respect thereto; processing the distances and directions between the agent and each other locally spaced agent; and 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.
In addition to the above, the method may further comprise the steps of designating one of the plurality of agents to act as a blocking beacon; preventing movement of the agent designated to act as a blocking beacon; and 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.
The step of processing the distances between the agent and each other locally spaced agent may be performed by providing an attraction/repulsion map for each agent, including an attraction region and a repulsion region; for each other locally spaced agent, determining, 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, generating 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, generating a vector representing the repulsion of the agent from the locally spaced agent; using 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.
Additionally, the step of processing the distances between the agent and each other locally spaced agent may further include the steps of providing a neutral region to the attraction/repulsion map for each agent; and 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.
In a further step, the attraction, repulsion, and neutral region may be configured 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. This aids in causing each one of the plurality of agents to maintain a predetermined distance from each other agent locally spaced therefrom. The regions may be defined as functions that decrease in a particular direction. For example, in the attraction region, the attraction may be tailored such that it becomes stronger with increasing distance, while in the repulsion region, the repulsion may be tailored such that it becomes weaker with increasing distance.
Among the agents, one may be designated as a leader, and the attraction/repulsion map for the leader may be adjusted so 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.
The designation of the leader may be triggered by various events such as, for example, when the number of agents provided is insufficient to fill the area while maintaining the predetermined distance from each other. The designation of the leader may also be triggered explicitly by a user command.
The leader designation is defined as what starts the actual process of selecting a leader. The actual selection of a leader may be performed in many ways, a few examples of which include (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. The process of selecting a leader may be periodically repeated upon the occurrence of a triggering event. Additionally, once a leader is selected, it may be desirable for the leader to transmit a suppression signal for preventing the repetition of the leader designating step until the occurrence of a triggering event. The suppression signal may be 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. In addition, the suppression signal transmitted from the leader may be relayed away from the leader such that it indicates the approximate distance from the leader and is ineffective for preventing the repeti
Daily Mike
Hoff Bruce
Howard Mike
Lee Craig
Payton David W.
HRL Laboratories
Marc McDieunel
Tope-McKay & Associates
LandOfFree
Method and apparatus for controlling the movement of a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for controlling the movement of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for controlling the movement of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3052683