Method and apparatus for terrain reasoning with distributed embedded processing elements

• US 6,580,979 B2
• Filed: 07/10/2001
• Issued: 06/17/2003
• Est. Priority Date: 07/10/2000
• Status: Expired due to Fees

• Current Assignee: HRL Laboratories LLC A Limited Liability Company of Delaware
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Howard, Mike, Payton, David W., Lee, Craig, Daily, Mike, Hoff, Bruce
• Primary Examiner(s): Nguyen, Tan Q.
• Assistant Examiner(s): Tran, Dalena
• Application Number:
  US09/903,878
• Publication Number:
  US 20020138247A1
• Time in Patent Office: 707 Days
• Field of Search: 701/25, 701/202, 701/209, 455/518, 455/456, 455/507, 455/517, 455/521, 709/317, 709/313, 709/202
• US Class Current: 701/25
• 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 and apparatus for computing properties of a physical environment is provided, using a plurality of agents forming a distributed network embedded within the environment. The method comprises determining an initiating agent 200, transmitting a signal including a cumulative cost value to neighboring agents 202, and processing the signal at each neighboring agent to augment the cumulative cost value with local information 204. If multiple signals are received, determining which has the best cumulative cost value for generating a new signal 206, then treating the neighboring agent as an initiating agent 208 and transmitting the new signal to neighboring agents 208 and retaining the best augmented cost value in memory 210. Methods further include determining paths using shortest path computations, using dual gradients for aligning agents on a path between two reference agents, and discovering and converging agents on choke points.

Claims

1. A method for computing properties of a physical environment using a plurality of agents deployed within the physical environment, wherein each agent comprises, a communication capability, a processor coupled with the communication capability, and a memory connected with the processor, and wherein the plurality of agents make use of physical properties of inter-agent communication in order to form a distributed representation of non-local properties of the physical environment, the method comprising the steps of:

a. triggering at least one initiating agent;

b. transmitting a signal from the initiating agent to agents neighboring the initiating agent;

c. processing the signal at each of the neighboring agents with a cost value based on local properties along the respective path between the initiating agent and each neighboring agent;

d. selecting, from the signals received, a new signal to transmit;

e. treating the neighboring agent as an initiating agent of the processed signal, and repeating the transmitting and processing steps; and

f. at each agent, locally retaining at least one cumulative cost value representing information regarding non-local properties of the physical environment based on signals received.

2. A method for computing properties of a physical environment as set forth in claim 1, wherein in the processing step, the cost value is a hop count and where the hop count is incremented at each agent in the processing step to generate, at each agent, a cumulative hop count from the initiating agent.

3. A method for computing properties of a physical environment as set forth in claim 1, wherein the cumulative cost value is used in the determining step to determine, from the signals received, the new signal to transmit.

4. A method for computing properties of a physical environment as set forth in claim 3, wherein signals are periodically propagated across the plurality of agents from the initiating agent, wherein cost values retained from past signals are compared with a cost value from a current signal in order to determine the cost value with which to process the signal.

5. A method for computing properties of a physical environment as set forth in claim 3, wherein the communication paths between the agents are line of sight paths, whereby transmission of signals across the line of sight path is used to provide a representation of traversability along the paths.

6. A method for computing properties of a physical environment as set forth in claim 3, wherein the agents include means for storing the direction from which a particular signal was received across a communication path, and method further includes the step of comparing cost values for different paths between two agents and the step of storing the direction of the path with the best cost.

7. A method for computing properties of a physical environment as set forth in claim 4, wherein the step of processing the signal further comprises the additional sub-steps of:

a. time-stamping cost values as they are retained in memory;

b. designating the most recently retained time-stamped cost value for use in processing the signal; and

c. removing the time-stamped cost values from memory after a predetermined time has elapsed.

8. A method for computing properties of a physical environment as set forth in claim 7, wherein in retaining cost values in memory, a plurality of cost values are recorded and ranked from best to worst over time;

wherein the best cost value is designated for use in processing the signal; and

wherein when the time stamp of a cost value designated for use in processing the signal expires and the cost value is removed from memory, the next best cost value is designated for use in processing the signal.

9. A method for computing properties of a physical environment as set forth in claim 1, wherein the method further comprises an agent alignment step, where the agent alignment step comprises the sub-steps of:

a. selecting two agents from among the plurality of agents to act as reference agents;

b. generating cost gradients comprising vector representations of an optimal cost path between each agent among the plurality of agents and each reference agents;

c. summing the vectors at each agent to create a motion vector for the agent; and

d. moving the agents along the motion vector in order to align the agents along a path between the reference agents.

10. A method for computing properties of a physical environment as set forth in claim 9, wherein the agent alignment step is triggered upon the occurrence of a triggering event.

11. A method for computing properties of a physical environment as set forth in claim 9, wherein the agent alignment step comprises the sub-steps of:

a. selecting a convergence agent; and

b. urging the other agents toward the convergence agent, resulting in a local clustering of agents near the convergence agent.

12. A method for computing properties of a physical environment as set forth in claim 1, wherein the agents further include at least one sensor connected with the processor, with the sensor providing an output, and wherein cost value used in the signal processing step is developed using the output of the sensor.

13. A method for computing properties of a physical environment as set forth in claim 12, wherein the cost value is used in the determining step to determine from the signals received the new signal to transmit.

14. A method for computing properties of a physical environment as set forth in claim 13, wherein signals are periodically propagated across the plurality of agents from the initiating agent, including a current signal and at least one past signal, wherein cost values retained from past signals are compared with a cost value from the current signal in order to determine the cost value with which to process the signal.

15. A method for computing properties of a physical environment as set forth in claim 13, wherein the agents include means for storing the direction from which a particular signal was received across a communication path, and method further includes the step of comparing cost values for different paths between two agents and the step of storing the direction of the path with the best cost.

16. A method for computing properties of a physical environment as set forth in claim 14, wherein the step of processing the signal further comprises the additional sub-steps of:

a. time-stamping cost values as they are retained in memory;

b. designating the most recently retained time-stamped cost value for use in processing the signal; and

c. removing the time-stamped cost values from memory after a predetermined time has elapsed.

17. A method for computing properties of a physical environment as set forth in claim 16, wherein in retaining cost values in memory, a plurality of cost values are recorded over time;

and in the removing the time-stamped cost values from memory, another historic cost value is selected for adjusting the cumulative cost value message.

18. A method for computing properties of a physical environment as set forth in claim 13, wherein the communication paths between the agents are line of sight paths, whereby transmission of signals across the line of sight path is used to provide a representation of traversability along the paths.

19. A method for computing properties of a physical environment as set forth in claim 12, wherein the method further comprises an agent alignment step, where the agent alignment step comprises the sub-steps of:

a. selecting two agents from among the plurality of agents to act as reference agents;

b. generating cost gradients comprising vector representations of an optimal cost path between each agent among the plurality of agents and each reference agents;

c. summing the vectors at each agent to create a motion vector for the agent; and

d. moving the agents along the motion vector in order to align the agents along a path between the reference agents.

20. A method for computing properties of a physical environment as set forth in claim 19, wherein the agent alignment step is triggered upon the occurrence of a triggering event.

21. A method for computing properties of a physical environment as set forth in claim 20, wherein the agent alignment step comprises the sub-steps of:

a. selecting a convergence agent; and

b. urging the other agents toward the convergence agent, resulting in a local clustering of agents near the convergence agent.

22. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment, the agent comprising:

a. a communication capability for communicating with other, locally spaced agents from among the plurality of agents;

b. a processor coupled with the communication capability to generate a local cost value from the physical properties along the paths between the agent and each of the other locally spaced agents, to combine the local cost values with respective non-local cost values received in communication with each of the other locally spaced agents in order to generate cumulative cost values, to determine the best of the cumulative cost values, and to generate a new signal incorporating the best cumulative cost value for transmission to other locally spaced agents; and

c. a memory connected with the processor for retaining the best cumulative cost value, whereby the plurality of agents make use of physical properties of inter-agent communication in order to form a distributed representation of non-local properties of the physical environment, wherein at least one of the agents among the plurality of agents is designated as an initiating agent and propagates a signal across the plurality of agents, with the signal updated to incorporate the best cumulative cost value as it is propagated across the plurality of agents and away from the initiating agent, whereby a representation of the best path to the initiating agent is stored at each agent among the plurality of agents.

23. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 22, wherein in the non-local cost value is a hop count from an initiating agent, wherein the local cost value is an increment of the hop count, and wherein the cumulative cost value is generated in the processor by summing the best non-local cost value received at the agent with the local cost value, to produce an incremented hop count.

24. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 22, wherein the cumulative cost value is used in the processor to determine, from the signals received, the best cumulative cost value for transmission to other locally spaced agents.

25. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 24, wherein signals are periodically propagated across the plurality of agents from an initiating agent, and wherein cumulative cost values retained in the memory of the agent are compared with a cumulative cost value generated from a newly received signal in order to determine the best cumulative cost value for transmission to other locally spaced agents.

26. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 24, wherein the communication paths between the agents are line of sight paths, whereby transmission of signals across the line of sight path is used in the processor of the agent to generate a cumulative cost value representation of traversability along a path from an initiating agent to the agent.

27. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 24, wherein the agent further includes, connected with the memory, a means for determining the direction from which a particular signal was received across a communication path, wherein the direction from which the signal with the best cost value was received is stored in the memory.

28. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 25, wherein the processor is further operative to time stamp cumulative cost values as they are retained in memory;

to designate the most recently retained time-stamped cumulative cost value for use in processing the signal; and

to remove the time-stamped cumulative cost values from memory after a predetermined time has elapsed.

29. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 28, wherein a plurality of cumulative cost values are recorded in memory over time, and wherein when removing the time-stamped cumulative cost values from memory, the processor causes another cumulative cost value from memory to be selected for adjusting the cumulative cost value message.

30. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 22, wherein the agent furthers include at least one sensor connected with the processor, with the sensor providing an output, and wherein the local cost value is developed by the processor using the output of the sensor.

31. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 30, wherein the cumulative cost value is used in the processor to determine, from the signals received, the best cumulative cost value for transmission to other locally spaced agents.

32. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 31, wherein signals are periodically propagated across the plurality of agents from an initiating agent, and wherein cumulative cost values retained in the memory of the agent are compared with a cumulative cost value generated from a newly received signal in order to determine the best cumulative cost value for transmission to other locally spaced agents.

33. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 31, wherein the communication paths between the agents are line of sight paths, whereby transmission of signals across the line of sight path is used in the processor of the agent to generate a cumulative cost value representation of traversability along a path from an initiating agent to the agent.

34. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 31, wherein the agent further includes, connected with the memory, a means for determining the direction from which a particular signal was received across a communication path, wherein the direction from which the signal with the best cost value was received is stored in the memory.

35. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 32, wherein the processor is further operative to time stamp cumulative cost values as they are retained in memory;

to designate the most recently retained time-stamped cumulative cost value for use in processing the signal; and

to remove the time-stamped cumulative cost values from memory after a predetermined time has elapsed.

36. An agent for use among a plurality of agents deployed within the physical environment for computing properties of a physical environment as set forth in claim 35, wherein a plurality of cumulative cost values are recorded in memory over time, and wherein when removing the time-stamped cumulative cost values from memory, the processor causes another cumulative cost value from memory to be selected for adjusting the cumulative cost value message.