Spatial coordination system

• US 20020069018A1
• Filed: 07/06/2001
• Published: 06/06/2002
• Est. Priority Date: 07/07/2000
• Status: Active Grant

• Current Assignee: Techteam Government Solutions Incorporated (Jacobs Solutions, Inc.)
• Original Assignee: Techteam Government Solutions Incorporated (Jacobs Solutions, Inc.)
• Inventors: Brueckner, Sven, Sauter, John A., Parunak, Henry Van Dyke
• Granted Patent: US 7,415,313 B2
• Time in Patent Office: Days
• US Class Current: 701/300
• CPC Class Codes: B25J 9/1617 Cellular, reconfigurable manipulator, e.g. cebot
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A system and process uses pheromone propagation to provide direction and/or distance information to a remote destination through the use of localized decision making processes. Locally available information is exchanged and translated with global information through the use of a pheromone vocabulary and multi-layer grid systems. Self-organizing networks of sensors provide remote monitoring of a space.

Claims

1. A system for constraining the movement of a walker in a space with respect to some distinguished location in said space, comprising:

a pump associated with the distinguished location emitting a pheromone to generate a pheromone gradient, said pheromone having a rate of evaporation and a rate of propagation and

a walker operating in a grid system within the space and having a pheromone sensing threshold, said walker moving within the space to satisfy a preselected constraint with respect to said pump.

2. The system of claim 1 wherein the space is two-dimensional.

3. The system of claim 1 wherein the space is selected from the group consisting of:

virtual, three-dimensional and multi-dimensional with a dimensionality of greater than 3.

4. The system of claim 1 further comprising a plurality of said pumps.

5. The system of claim 1 wherein said pheromone is emitted at a fixed strength.

6. The system of claim 1 wherein said pheromone is emitted at regular intervals.

7. The system of claim 1 wherein said pump is stationary.

8. The system of claim 1 wherein said pump is mobile within the space.

9. The system of claim 1 wherein the rate of propagation is the same in all directions.

10. The system of claim 1 wherein the rate of propagation depends on a mesh of the grid system.

11. The system of claim 1 wherein the propagation is between 1 and 20 walker sensing steps.

12. The system of claim 1 wherein said grid system is selected from a group consisting of:

trigonal, quadragonal, irregular, and hexagonal.

13. The system of claim 1 wherein the grid system is hexagonal.

14. The system of claim 1 wherein the preselected constraint relative to said pump is co-location.

15. The system of claim 1 wherein the preselected constraint relative to said pump is a spacing having a preselected pheromone concentration.

16. The system of claim 15 wherein the preselected pheromone concentration is above the pheromone sensing threshold of said walker.

17. The system of claim 15 wherein the preselected pheromone concentration is below the pheromone sensing threshold of said walker.

18. The system of claim 1 wherein said pump emits a plurality of pheromones, said plurality of pheromones having a plurality of rates of propagation and said walker senses each of said plurality of pheromones differently.

19. The system of claim 1 wherein said grid system is a multi-layer grid system.

20. The system of claim 19 wherein the multi-layer grid system comprises layers that vary in relative mesh.

21. A process for constraining the movement of a walker in a space with respect to some distinguished location in said space, comprising the steps of:

emitting a pheromone from a pump to generate a pheromone gradient, wherein said pheromone has a rate of evaporation and rate of propagation; and

moving a walker within the space in response to the pheromone gradient to satisfy a preselected constraint relative to said pump.

22. The process of claim 21 wherein the movement of said walker follows a polytopal grid system.

23. The process of claim 22 wherein the grid system is selected from a group consisting of trigonal, quadragonal, irregular, and hexagonal,.

24. The process of claim 23 wherein the grid system is hexagonal and a sum of said pheromone deposited in a grid system place that is reached from the pump'"'"'s place p₀ in d steps and the shortest path of the grid system, t time units after emission is computed recursively as

25. The process of claim 21 wherein the movement of said walker further comprises the step of determining a selection probability for moving a grid system unit adjacent to a walker place.

26. The process of claim 25 wherein determining the selection probability further comprises the steps of:

sampling a concentration of said pheromone, s_i at each adjacent place p_i; and

determining the relative attraction, f_i of an adjacent place normalized by an overall concentration of all places as given by the equation

$f_i=s_i/\underset{p_j\in <br><br>\text{\hspace{1em}<br><br>}<br><br>C<br><br>\left(p\right)}{\sum <br><br>}<br><br>s_j$

where C(p) is the current place of said walker and the directly adjacent grid system units of said walker and _j denotes all grid system units sampled.

27. The process of claim 21 wherein emission of a pheromone further comprises emitting a second pheromone having a second propagation distance that varies from the propagation distance of said pheromone.

28. The process of claim 21 wherein the preselected location of said walker relative to said pump is co-location.

29. The process of claim 21 wherein emission of said pheromone is from a plurality of pumps within the space.

30. The process of claim 21 wherein movement of said walker in the space is random until said walker senses said pheromone gradient.

31. The process of claim 27 wherein the movement of said walker is along a multi-layer grid system.

32. The process of claim 31 wherein said second pheromone is emitted differentially within the multi-layer grid system relative to said pheromone.

33. The process of claim 31 further comprising the step of said walker following said second pheromone preferentially when remote from said pump and said pheromone preferentially when proximal to said pump.

35. The system of claim 34 wherein the space is two-dimensional.

36. The system of claim 34 wherein the space is selected from the group consisting of:

virtual, three-dimensional and multi-dimensional with a dimensionality of greater than 3.

37. The system of claim 34 further comprising a plurality of said pumps.

38. The system of claim 34 wherein said pump is mobile within the space.

39. The system of claim 34 wherein the preselected constraint relative to said pump is co-location.

40. The system of claim 34 wherein said polygonal grid system is a multi-layer grid system.

34. A system for constraining the movement of a walker in a space with respect to some distinguished location in said space, comprising:

a pump;

a plurality of distance agents created by said pump around a pump location, said plurality of distance agents depositing distance-pheromones having local concentrations forming a distance profile; and

a walker operating in a grid space of polytopes that samples the distance profiles to satisfy a preselected constraint relative to said pump.

41. A process for determining the location of an object in a space comprising:

creating a field of distance agents around a pump;

depositing distance-pheromones from said distance agents, the local concentration of said distance-pheromones forming a distance profile;

sampling the distance profiles by a walker; and

triangulating the location of said pump associated with the object.

42. The process of claim 41 wherein said pump is mobile.

43. The process of claim 41 wherein said walker samples the distance profiles using a strategy selected from the group consisting of minimal distance and minimal distance weighted by pump concentration.

44. The process of claim 41 further comprising relocating of said pump.

45. The process of claim 44 wherein the relocation of said pump comprises the steps of:

canceling the current distance agent field;

canceling the regular deposit of a distance-pheromone;

registration at the current place;

deregistering from the current place;

registering in a new place;

registering a regular deposit of distance-pheromone in the new place; and

establishing a new distance agent field.

46. The process of claim 43 wherein said walker follows a minimum distance weighted by pump concentration relocation strategy and the relative attraction f_j of a place p_j in C(p) is

48. The use of claim 47 wherein the multi-layer grid has at least two mesh sizes.

50. The infrastructure of claim 49 wherein each of the plurality of places emits a continuous signal that transmits place coordinates.

51. The infrastructure of claim 49 wherein each of said plurality of places assumes a radius of sensing responsibility related to proximity of neighboring places.

52. The infrastructure of claim 49 wherein said seeker is directed to said target with a guidance vector.

47. The use of a multi-layer grid system to direct a walker through a multi-pheromone environment where said walker is able to sense the multi-pheromones.

49. A self-organizing pheromone infrastructure comprising:

a plurality of processing node places scattered in a space, each of said plurality of places capable of interacting by short range communication with nearby places, said plurality of places having sensors;

at least one target within the space being detected by one of the sensors within one of the places; and

a mobile target seeker in direct communication with at least one of the plurality of places to direct said seeker to said target.

53. An undirected coordination system comprising:

a plurality of small robots spatially distributed in a space, each of said plurality of s-bots exchanging messages with neighboring s-bots by short range communication; and

a plurality of anchors less than the plurality of s-bots, said plurality of anchors in communication with said plurality of s-bots through a guidance field.

54. The coordination system of claim 53 wherein each of said plurality of s-bots estimates an absolute geographic location therefor independent of inputs external to the space.

55. The coordination system of claim 53 wherein one of said plurality of anchors comprises long range communication equipment extendable outside of the space.