Exhaustive search system and method using space-filling curves
AssigneeSandia Corporation
InventorShannon V. Spires
Life of this patent
Estimating the term…
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.
Claims25
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.
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.
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.
Dependencies are inferred from the claim text.