Opportunistic connectivity edge detection

• US 8,879,426 B1
• Filed: 09/03/2010
• Issued: 11/04/2014
• Est. Priority Date: 09/03/2009
• Status: Active Grant

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Quilling, Mark L., Bose, Prasanta, Payne, Ken, Zimdars, Andrew
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): LEE, ANDREW CHUNG CHEUNG
• Application Number:
  US12/876,045
• Time in Patent Office: 1,523 Days
• Field of Search: 370/245, 370/255, 370/256, 700/250, 700/251, 700/252, 700/253
• US Class Current: 370/255
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 84/005 Moving wireless networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A distributed coordination and control protocol may enable a set of mobile, self-organizing, robotic relay nodes to adaptively seek positions in such an environment that establishes a network, meeting desired coverage in terms of connected warfighters. Distributed coordination of robotic relay nodes may allow the network to dynamically adapt as positions of warfighters change and/or the network demands change. An algorithm is provided that may be scalable to a large number of robots and may be robust to random deployment of robots, robot platform failures, channel dynamics, and changing warfighter positions.

Claims

1. A self-configuring communications mesh network infrastructure comprising:

a plurality of robotic radio relay nodes configured for self-configuration movement and radio transmission and reception as part of a mesh network;

a robot agent configured to execute tactics and skills associated with the plurality of robotic radio relay nodes; and

a robot control platform configured to control the plurality of robotic radio relay nodes, wherein control of the plurality of robotic radio relay nodes comprises;

selection of a multi-robot play that includes coordinated movement of one or more robotic radio relay nodes;

maintenance of a distributed map of a location of the plurality of robotic radio relay nodes; and

control over a transmit power and link data rate of the plurality of robotic radio relay nodes.

2. The self-configuring communications mesh network infrastructure of claim 1, comprising a gateway configured to form a wireless link to one or more of the plurality of robotic radio relay nodes and to link to another gateway.

3. The self-configuring communications mesh network infrastructure of claim 1, wherein control of the plurality of robotic radio relay nodes comprises control of optimization of the mesh network.

4. The self-configuring communications mesh network infrastructure of claim 3, wherein optimization comprises one or more of the robotic radio relay nodes moving according to a spoker tactic.

5. The self-configuring communications mesh network infrastructure of claim 1, wherein the robot control platform is configured to receive sensor data from the plurality of robotic radio relay nodes.

6. The self-configuring communications mesh network infrastructure of claim 1, wherein the robotic control platform comprises a link state manager configured to store data regarding link states of the plurality of robotic radio relay nodes.

7. The self-configuring communications mesh network infrastructure of claim 6, wherein the link state manager comprises a database.

8. The self-configuring communications mesh network infrastructure of claim 1, wherein the robotic control platform comprises a hierarchical, hypothetical, and opportunistic (H2O) state manager configured to store data regarding hierarchical, hypothetical, and opportunistic (H2O) states of the plurality of robotic radio relay nodes.

9. The self-configuring communications mesh network infrastructure of claim 8, wherein the a H2O state manager comprises a database.

10. The self-configuring communications mesh network infrastructure of claim 1, wherein the robotic control platform comprises a robot state manager configured to store data regarding physical environment of each of the plurality of robotic radio relay nodes.

11. The self-configuring communications mesh network infrastructure of claim 10, wherein the robot state manager comprises a database.

12. The self-configuring communications mesh network infrastructure of claim 1, wherein the robotic control platform comprises a skills, tactics and plays for exploration and relay (STPERS) state manager configured to store data regarding multi-robot behavior of the plurality of robotic radio relay nodes.

13. The self-configuring communications mesh network infrastructure of claim 12, wherein the skills, tactics and plays for exploration and relay (STPERS) state manager comprises a database.

14. The self-configuring communications mesh network infrastructure of claim 1, wherein the plurality of robotic radio relay nodes are configured to operate as state machines.

15. The self-configuring communications mesh network infrastructure of claim 1, comprising a STPER agent configured to choose a tactic to execute and to command the robot agent to load the tactic.

16. A method of controlling a self-configuring communications mesh network infrastructure including (i) a plurality of robotic radio relay nodes configured for self-configuration movement and radio transmission and reception as part of the mesh network, and (ii) a robot control platform configured to control the plurality of robotic radio relay nodes, the method comprising:

selecting a multi-robot play that includes coordinated movement of two or more robotic radio relay nodes of the plurality of robotic radio relay nodes of the mesh network;

maintaining a distributed map of a location of the plurality of robotic radio relay nodes;

controlling a transmit power and link data rate of the plurality of robotic radio relay nodes;

causing execution of tactics and skills associated with the plurality of robotic radio relay nodes; and

causing selection of a tactic to execute and to command loading of the tactic.

17. The method of claim 16, wherein maintaining a distributed map of a location of the plurality of robotic radio relay nodes comprises maintaining information about radio frequency (RF) environment at the respective locations of the plurality of robotic radio relay nodes.

18. The method of claim 16, comprising using a gateway to form a communications link to one or more of the plurality of robotic radio relay nodes, wherein the gateway is configured to form a wireless link to one or more of the plurality of robotic radio relay nodes and to link to another gateway.

19. The method of claim 16, comprising controlling optimization of the mesh network.

20. The method of claim 19, wherein optimization comprises one or more of the robotic radio relay nodes moving according to a spoker tactic.

21. The method of claim 19, wherein optimization comprises computing an optimal spanning tree for movement of one or more of the plurality of robotic radio relay nodes.

22. The method of claim 16, wherein the robot control platform is configured to receive sensor data from the plurality of robotic radio relay nodes.

23. The method of claim 16, wherein the robotic control platform comprises a link state manager configured to store data regarding link states of the plurality of robotic radio relay nodes.

24. The method of claim 16, wherein the robotic control platform comprises a hierarchical, hypothetical, and opportunistic (H2O) state manager configured to store data regarding hierarchical, hypothetical, and opportunistic (H2O) states of the plurality of robotic radio relay nodes.

25. The method of claim 16, wherein the robotic control platform comprises a robot state manager configured to store data regarding physical environment of each of the plurality of robotic radio relay nodes.

26. The method of claim 16, wherein the robotic control platform comprises a skills, tactics and plays for exploration and relay (STPERS) state manager configured to store data regarding multi-robot behavior of the plurality of robotic radio relay nodes.

27. The method of claim 16, wherein the plurality of robotic radio relay nodes are configured to operate as state machines.

28. The method of claim 16, wherein causing execution of tactics and skills comprises causing a robot agent to execute the tactics and skills associated with the plurality of robotic radio relay nodes.

29. The method of claim 28, wherein causing selection of the tactic comprises causing a STPER agent to choose a tactic to execute and to command the robot agent to load the tactic.

30. The method of claim 16, comprising implementing a hierarchical, hypothetical, and opportunistic (H2O) algorithm for one or more of the plurality of robotic radio relay nodes.

31. The method of claim 30, wherein the H2O algorithm comprises position estimation.

32. The method of claim 30, wherein the H2O algorithm comprises area type and size computation.

33. The method of claim 30, wherein the H2O algorithm comprises local feature extraction.

34. The method of claim 30, wherein the H2O algorithm comprises wall segments and loop detection.

35. The method of claim 30, wherein the H2O algorithm comprises optimal spanning tree computation.

36. The method of claim 35, wherein optimal spanning tree computation comprises an approximate Steiner Tree (AST) algorithm.

37. The method of claim 16, wherein selecting a multi-robot play comprises selecting an initialization play.

38. The method of claim 16, wherein selecting a multi-robot play comprises selecting an opportunistic connectivity edge detection (OCED) play.

39. A non-transitory machine-readable medium with machine-readable instructions for controlling a self-configuring communications mesh network infrastructure including (i) a plurality of robotic radio relay nodes configured for self-configuration movement and radio transmission and reception as part of the mesh network, and (ii) a robot control platform configured to control the plurality of robotic radio relay nodes, the machine-readable instructions executable to:

select a multi-robot play that includes coordinated movement of two or more robotic radio relay nodes of the plurality of robotic radio relay nodes of the mesh network, the multi-robot play comprising an opportunistic connectivity edge detection (OCED) play;

maintain a distributed map of a location of the plurality of robotic radio relay nodes; and

control a transmit power and link data rate of the plurality of robotic radio relay nodes.

40. The non-transitory machine-readable medium of claim 39, wherein the machine-readable instructions executable to maintain a distributed map of the location of the plurality of robotic radio relay nodes comprises machine-readable instructions executable to maintain information about radio frequency (RF) environment at the respective locations of the plurality of robotic radio relay nodes.

41. The non-transitory machine-readable medium of claim 39, wherein the machine-readable instructions are executable to use a gateway to form a communications link to one or more of the plurality of robotic radio relay nodes, wherein the gateway is configured to form a wireless link to one or more of the plurality of robotic radio relay nodes and to link to another gateway.

42. The non-transitory machine-readable medium of claim 39, wherein the machine-readable instructions are executable to optimize the mesh network.

43. The non-transitory machine-readable medium of claim 42, wherein the machine-readable instructions are executable to cause one or more of the robotic radio relay nodes to move according to a spoker tactic.

44. The non-transitory machine-readable medium of claim 42, wherein the machine-readable instructions executable to optimize the mesh network comprises machine-readable instructions executable to compute an optimal spanning tree for movement of one or more of the plurality of robotic radio relay nodes.

45. The non-transitory machine-readable medium of claim 39, wherein the machine-readable instructions are executable to cause a robot agent to execute tactics and skills associated with the plurality of robotic radio relay nodes.

46. The non-transitory machine-readable medium of claim 45, wherein the machine-readable instructions are executable to cause a STPER agent to choose a tactic to execute and to command the robot agent to load the tactic.

47. The non-transitory machine-readable medium of claim 39, wherein the machine-readable instructions are executable to implement a hierarchical, hypothetical, and opportunistic (H2O) algorithm for one or more of the plurality of robotic radio relay nodes.

48. The non-transitory machine-readable medium of claim 47, wherein the H2O algorithm comprises position estimation.

49. The non-transitory machine-readable medium of claim 47, wherein the H2O algorithm comprises area type and size computation.

50. The non-transitory machine-readable medium of claim 47, wherein the H2O algorithm comprises local feature extraction.

51. The non-transitory machine-readable medium of claim 47, wherein the H2O algorithm comprises wall segments and loop detection.

52. The non-transitory machine-readable medium of claim 47, wherein the H2O algorithm comprises optimal spanning tree computation.

53. The non-transitory machine-readable medium of claim 52, wherein optimal spanning tree computation comprises an approximate Steiner Tree (AST) algorithm.

54. A robot configured for operation within a self-configuring communications mesh network, the robot comprising:

a radio frequency (RF) system configured as a network node to receive and transmit RF communications from a network;

a sensor system configured to sense physical conditions of the environment of the robot;

a locomotion system configured to move the robot in a desired direction; and

a control system configured to receive signal from the sensor system and to control the RF system and the locomotion system according to an opportunistic connectivity edge detection (OCED) algorithm, wherein the robot is configured to explore a deployment region and to connect to a self-configuring communications mesh network.

55. The network robot of claim 54, wherein the OCED algorithm comprises connecting to another network node according to a FIND_CLUSTERS state.

56. The robot of claim 54, wherein the OCED algorithm comprises a SR_SEARCH state, wherein the robot is configured to have a connection to at least one stationary relay (SR) in the mesh network, and wherein the robot is configured to move until the robot loses all connectivity to the at least one stationary relay (SR) and continuously measure received signal strength indication (RSSI) to find boundaries of the connectivity region for each stationary relay (SR).

57. The robot of claim 54, wherein the OCED algorithm comprises a TRANSFER_WALL state, wherein the robot is configured to move in a direction until it bumps into an object, and wherein the robot is configured to then change course.

58. The robot of claim 54, wherein the sensor system comprises a bump sensor.

59. The robot of claim 58, wherein the bump sensor comprises an accelerometer.

60. The robot of claim 54, wherein the OCED algorithm comprises a REGAIN_SR state, wherein the robot is configured to backtrack a previous course to regain a connection to a stationary relay (SR).

61. The robot of claim 54, wherein the OCED algorithm comprises a SR_CHECKS state, wherein the robot is configured to check link quality, failed nodes, and connectivity.

62. The robot of claim 61, wherein the robot is configured to monitor received signal strength indication (RSSI) to each of its next hop neighbors that are stationary relays (SRs).