Data processing: vehicles – navigation – and relative location – Vehicle control – guidance – operation – or indication – Automatic route guidance vehicle
Reexamination Certificate
2001-07-10
2003-06-17
Nguyen, Tan Q. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Vehicle control, guidance, operation, or indication
Automatic route guidance vehicle
C701S202000, C709S241000, C709S241000
Reexamination Certificate
active
06580979
ABSTRACT:
TECHNICAL FIELD
The present invention is related to the field of computing properties of a physical environment. More specifically, this disclosure presents a method for computing properties of a physical environment using a plurality of agents forming a distributed network embedded within the environment.
BACKGROUND
Over the past decades, approaches to path planning and terrain analysis have focused on single or parallel processor solutions operating on an internal map containing terrain features. Traditional terrain analysis came in one of two forms: 1) a single mobile agent (e.g. a robot), or a small number of agents, collecting terrain information on-the-fly and/or using a pre-constructed digital map to aid in path planning or other terrain-related decision making, and 2) simulated terrain-embedded entities (e.g. military vehicles in a simulated battlefield or simulated opponents in a computer game) referring to a terrain/environment database (which is an integral part of such simulations) as a pre-constructed map available for their geometric computations. Typical computations include determination of the shortest path to a destination, of high visibility locations in the terrain, and of routes concealed from known opponent locations. In these traditional approaches to route planning and terrain reasoning, relevant data are taken from the real world to build a map readable by a machine. Terrain/environmental reasoning based on local sensing provides very limited access to environmental information. The natural solution is to pre-construct a map of the environment, which provides much more information and may be updated by information from a robot's own sensors. Such maps are usually represented by an array of terrain features including traversability and blocked routes that can be translated into a corresponding array of mobility costs representative of the difficulty and expense to move across a particular terrain path. The cost array can then be analyzed to obtain a new map, which indicates minimum cost paths between designated points on the map. In this traditional approach, the separate and distinct steps of sensing environmental features of the area, transmitting data to a central point, and generating a map must be performed before any minimum cost path computations can take place. As a result, it is often difficult to determine up to date minimum cost paths in situations where the environment is rapidly changing, or where sensing and map generation cannot be performed on a timely basis.
Current means of mapping a space include use of a few powerful mobile robots moving through an environment in a search pattern, sending raw or partially processed data back to a central computing resource. The central resource compiles a map and then operates on it. Dynamic changes to the environment are not picked up unless the robots repeat their search. Some communication networks perform computations to determine lowest cost paths for communications purposes (e.g., to minimize transmission energy or delays due to signal retransmission). These approaches are concerned specifically with communication issues, and they do not attempt to draw any correspondence between communications efficiency and properties of the environment that might impact mobility. Relevant information to some of these approaches can be found in U.S. Pat. Nos. 5,561,790 and 5,233,604.
Thus, it would be desirable to provide a means for determining optimal paths over or through an area of an environment by using a large number of small, inexpensive agents, requiring only local communications with neighboring agents. Signals would be transmitted across paths through the plurality of agents in a series of hops in a manner that provides, at each agent, a local representation of the cumulative non-local properties along a path. The information in the agents could be quickly updated by transmitting another signal along the path.
SUMMARY OF THE PRESENT INVENTION
The invention disclosed herein provides a method and apparatus for computing properties of a physical environment using a plurality of agents deployed within the physical environment. Each agent deployed comprises, a communication capability, a processor coupled with the communication capability, and a memory connected with the processor. The plurality of agents makes 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 of the present invention comprises the steps of of triggering at least one initiating agent; transmitting a signal from the initiating agent to agents neighboring the initiating agent; 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; selecting, from the signals received, a new signal to transmit; treating the neighboring agent as an initiating agent of the processed signal, and repeating the transmitting and processing steps; and 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. Thus, as a signal propagates. from an initiating agent to each agent among the plurality of agents, a cumulative cost value is stored at each agent in order to provide a measure of the quality of the best path from that agent to the initiating agent.
The cost value may be represented as a simple hop count, iterated with each hop as the signal propagates across the plurality of agents from the initiating agent. The cumulative cost value is typically used to determine from the signals received, the new signal to transmit. Additionally, cost values may be retained from past signals and compared with the cost value from the current signal in order to determine the cost value with which to process the signal. The signals are typically passed along line of sight paths, which provide a general representation of the traversability along a path.
The agents may also be augmented by providing them with a means for storing the direction from which a particular signal was received across a communication path, and the cost values for different paths between two agents may be stored along with the corresponding direction to the path with the best cost.
Additionally, the cost values may be time stamped as they are retained in the memory of the agents, with the most recently retained cost value being designated for use in processing the signal, and with the cost values being removed from memory after a predetermined time has elapsed. The cost values may also be ranked from best to worst over time, with the best cost value used in processing the signal. In this case, 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.
In another embodiment of the present invention, the agents may be configured to perform an alignment, wherein two agents are selected from among the plurality of agents to act as reference agents; cost gradients comprising vector representations of an optimal cost path between each agent among the plurality of agents and each reference agents are generated; the vectors are summed at each agent to create a motion vector for the agent; and the agents are moved along the motion vector in order to align the agents along a path between the reference agents. The alignment step may be triggered upon the occurrence of a triggering event such, for example, the detection of an intruder. Once the agents have aligned along a path, they may be converged to a choke point by selecting a convergence agent and urging the other agents toward the convergence agent, resulting in a local clustering of agents near the convergence agent.
The agents may also incorporate sensors connected with their processors in order to provide additional information to the processor for t
Daily Mike
Hoff Bruce
Howard Mike
Lee Craig
Payton David W.
HRL Laboratories LLC
Nguyen Tan Q.
Tope-McKay & Associates
Tran Dalena
LandOfFree
Method and apparatus for terrain reasoning with distributed... 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 terrain reasoning with distributed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for terrain reasoning with distributed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3118329