Exhaustive search system and method using space-filling curves

• US 6,636,847 B1
• Filed: 06/29/2000
• Issued: 10/21/2003
• Est. Priority Date: 07/01/1999
• Status: Active Grant

• Current Assignee: National Technology & Engineering Solutions Of Sandia LLC (Honeywell International Inc.)
• Original Assignee: Sandia Corporation (Martin Marietta Corporation)
• Inventors: Spires, Shannon V.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): FILIPCZYK, MARCIN R
• Application Number:
  US09/608,335
• Time in Patent Office: 1,209 Days
• Field of Search: 707/2, 707/3, 707/6, 707/10, 706/45, 706/4
• US Class Current: 707/770
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A search system and method for one agent or for multiple agents using a space-filling curve provides a way to control one or more agents to cover an area of any space of any dimensionality using an exhaustive search pattern. An example of the space-filling curve is a Hilbert curve. The search area can be a physical geography, a cyberspace search area, or an area searchable by computing resources. The search agent can be one or more physical agents, such as a robot, and can be software agents for searching cyberspace.

Claims

1. A distributed search system for controlling two or more agents to exhaustively search an area in parallel as a coordinated, coherent communicating group, wherein the distributed search system comprises an agent search system associated with each agent, and wherein each agent search system comprises:

a) a locator, in communication with the agent;

b) a search controller, responsive to the locator and generating an exhaustive search pattern for the search area comprising a space-filling curve along which the agent travels; and

c) means for communicating information with other agents.

2. The distributed search system of claim 1, wherein the space-filling curve comprises a Hilbert curve.

3. The distributed search system of claim 1, wherein the search area comprises a physical geography, and wherein each agent comprises a robot.

4. The distributed search system of claim 3, wherein said means for communicating comprises one or more communication means selected from the group consisting of means for dropping a marker or token and means for detecting a marker or token.

5. The distributed search system of claim 1, wherein the locator of each agent search system comprises a position identifier and a target sensor.

6. The distributed search system of claim 5, wherein the position identifier of each agent search system'"'"'s locator is selected from the group consisting of:

inertial sensors, inertial position units, global positioning systems, initial position identifiers, dead-reckoning, cyberspace addresses, IP addresses, and combinations thereof.

7. The distributed search system of claim 1, wherein the search area comprises a cyberspace search area.

8. The distributed search system of claim 1, wherein the search controller of each agent search system comprises:

a) a computer, responsive to the locator,

b) a communicator, accessible from the computer and communicating an initial position for the agent; and

c) a program implementing the exhaustive search pattern on the computer.

9. The distributed search system of claim 1, wherein the search controller of each agent search system comprises:

a) an initalizer, responsive to the locator;

b) a searcher, generating the exhaustive search pattern; and

c) a terminator, indicating a termination condition for the search controller.

10. The distributed search system of claim 9, wherein the initializer of each agent search system'"'"'s controller comprises;

a) means for determining an initial position for the agent, indicated by the locator; and

b) means for determining an identified extrema position of the search area.

11. The distributed search system of claim 10, wherein each agent has an associated agent coverage size, and wherein the initializer of each agent search system'"'"'s controller further comprises a search pattern parameter, determined from the identified extrema position and the agent coverage size.

12. The distributed search system of claim 1, wherein each agent searches along the same space-filling curve.

13. A computer-implemented method for controlling two or more agents to exhaustively search an area as a coordinated, coherent communicating group, wherein each agent comprises a locator and a search controller, wherein the method, for each agent, acting in parallel with the other agents, comprises:

a) determining a characteristic of the agent from the locator;

b) searching the search area, according to a space-filling curve and the characteristic;

c) communicating information with other agents; and

d) terminating the search controller, according to a termination condition.

14. The method of claim 13,

a) wherein the characteristic comprises:

i) an initial position for the agent; and

ii) an extreme position of the search area;

b) and the method further comprises communicating the initial position with other agents in the two or more agents.

15. The method of claim 14, wherein each agent has an associated agent coverage size, the method further comprising generating a search pattern parameter, determined from the extreme position and the agent coverage size, and indicative of the space-filling curve.

16. The method of claim 13, wherein the termination condition comprises a current agent position selected from the group consisting of:

an initial position for a preceding agent, a terminal position for a follower agent, initial position for the agent, a position along the space-filling curve, and combinations thereof.

17. The method of claim 13, wherein searching the search area comprises:

a) transforming a current position in a multi-dimensional space to a one-dimensional position along the space-filling curve;

b) incrementing the position along the space-filling curve; and

c) transforming the incremented position along the space-filling curve to a successor position in the multi-dimensional space.

18. The method of claim 13, wherein the two or more agents are selected from the group consisting of:

robots, cyberspace agents, software agents, search agents, coverage agents, and combinations thereof.

19. The method of claim 13, wherein communicating information with other agents comprises performing one or more tasks selected from the group consisting of dropping a marker or token and detecting a marker or token dropped at the beginning or end of an immediate neighbor agent'"'"'s path to communicate an “

all done”

signal without performing any broadcast communications.

20. A computer-implemented method for controlling two or more agents to exhaustively search an area in parallel as a coordinated, coherent communicating group, wherein each agent comprises a locator and a search controller;

wherein the method, for each agent, comprises;

a) locating its initial position;

b) computing a subregion size;

c) communicating its initial position with other agents;

d) determining extrema position of the search area if not already known;

e) determining self-position in search area;

f) determining search parameters based on the search area and subregion size;

g) determining number of subregions and length of a space-filling curve;

h) locating self on the space-filling curve;

i) searching along the space-filling curve until a termination condition is met;

j) communicating an “

all done”

signal and communicating search output;

k) continuing to search along the space-filling curve if its preceding agent has not communicated an “

all done”

signal; and

l) repeating steps i) through k) until an exhaustive search has been completed.

21. The method of claim 20, wherein the number of subregions in the search area is related to the length of the space-filling curve, Length_curve, according to:

22. The method of claim 20, wherein the space-filling curve comprises a Hilbert curve.

23. The method of claim 20, wherein the search area comprises a physical geography, and each agent comprises a robot.

24. The method of claim 23, wherein searching comprises traveling through the search area and leaving or removing something.

25. The method of claim 24, wherein leaving or removing something comprises performing one or more tasks selected from the group consisting of:

applying paint or fertilizer to a surface, mowing a lawn, maintaining a golf course, cleaning a swimming pool, and moving or clearing earth.