Apparatus and method of sensor deployment

• US 10,112,300 B2
• Filed: 03/10/2016
• Issued: 10/30/2018
• Est. Priority Date: 02/25/2016
• Status: Active Grant

• Current Assignee: King Fahd University Of Petroleum And Minerals
• Original Assignee: King Fahd University Of Petroleum And Minerals
• Inventors: Baroudi, Uthman, Haque, Md. Enamul, Azharuddin, Mohammed
• Primary Examiner(s): Tran, Dalena
• Application Number:
  US15/066,821
• Publication Number:
  US 20170246742A1
• Time in Patent Office: 964 Days
• Field of Search: 700257, 700258, 701 2, 701 24, 701117, 134172, 134 56 R, 901 1, 901 46
• CPC Class Codes: B25J 9/1664 characterised by motion, path, trajectory planning
• CPC Class Codes: H04W 4/70 Services for machine-to-machine communication [M2M] or machine type communication [MTC]
• CPC Class Codes: Y10S 901/01 Mobile robot

Abstract

Described herein is a method of deploying sensors by a robot in a geographical region. The robot receives a first instruction including information corresponding to the geographical region and a second instruction indicating one of a first manner and a second manner of deploying sensors. The robot computes a path to traverse the region in a plurality of steps, each step of the plurality of steps having a predetermined magnitude. The robot traverses until a stopping condition is satisfied. The robot deploys sensors at each traversed step size and further receives from each deployed sensor, information indicating absence of sensors in a neighboring area of the deployed sensor. Additionally, the robot repeats the traversing and deploying of sensors in the neighboring area to provide full coverage.

Claims

1. A method of deploying sensors by a robot in a geographical region, the method comprising:

receiving from a server, a first instruction including information corresponding to the geographical region, the information including at least a plurality of boundary locations of the geographical region and a first coordinate of the geographical region corresponding to a starting location for sensor deployment;

receiving from the server, a second instruction indicating one of a first manner and a second manner of deploying sensors in the geographical region;

computing by circuitry, based on the second instruction, a path to traverse the geographical region in a plurality of steps, each step of the plurality of steps having a predetermined magnitude, the traversing being performed until one of a first stopping criteria corresponding to the first manner of deploying sensors and a second stopping criteria corresponding to the second manner of deploying sensors being satisfied;

deploying sensors in the geographical region at each traversed step size;

receiving from each deployed sensor, information indicating absence of sensors in a neighboring area of the deployed sensor;

repeating the traversing and deploying of sensors in the neighboring area based on the received information until all corners of the geographical region have been visited at least once, and

checking for any available empty neighboring area, wherein checking for any available empty neighboring area includes

receiving, from one or more of the sensors, empty neighboring area information from the sensor adjacent to the empty neighboring area, the empty neighboring area information including a first location corresponding to the sensor adjacent to the empty neighboring area, ID of the sensor adjacent to the empty neighboring area, and a second location corresponding to the empty neighboring area, and

deploying sensors, wherein deploying sensors starts from the first location received from the sensor adjacent to the empty neighboring area,

wherein a total distance traversed by the robot in the first manner of deploying sensors is 2n(m+1)/l+m, wherein m is a width of the geographical region, n is a length of the geographical region, and l is a sensing range of the sensor,

wherein the robot traces its path backwards to its last known starting point and further adds an offset as a step size for the robot to proceed when the robot encounters an obstacle or boundary of the geographical region.

2. The method of claim 1, wherein the second instruction includes one of the first manner and the second manner of deploying sensors in the geographical region based on an orientation of a plurality of obstacles in the geographical region.

3. The method of claim 1, wherein the predetermined magnitude of the step size is equal to a sensing range of the sensors.

4. The method of claim 1, further comprising:

traversing to the first coordinate of the geographical region based on one of the first stopping criteria and the second stopping criteria being satisfied.

5. The method of claim 1, wherein the received information includes an identification number and a coordinate position of the deployed sensor.

6. The method of claim 1, wherein the first stopping criteria corresponding to the first manner of deploying sensors is satisfied upon the robot traversing each corner of the geographical region at least once.

7. The method of claim 1, wherein the second stopping criteria corresponding to the second manner of deploying sensors is satisfied upon the robot traversing each corner of the geographical region exactly once.

8. The method of claim 1, wherein the first manner of deploying sensors in the geographical area further comprising:

traversing by the step size, in an upward direction to a second location;

moving in a right direction from the second location; and

traversing back to the second location based on encountering one of an obstacle and a boundary of the geographical region.

9. The method of claim 1, wherein the second manner of deploying sensors in the geographical area further comprising:

traversing by the step size in a first direction;

moving in an upward direction based on encountering one of an obstacle and a boundary of the geographical region; and

traversing by the step size in a second direction, the second direction being opposite to the first direction.

10. The method of claim 1, wherein a total distance traversed by the robot in the second manner of deploying sensors is n*(m+1)/l+m, wherein m is a width of the geographical region, n is a length of the geographical region, and l is a sensing range of the sensor.

11. A non-transitory computer readable medium having stored thereon a program that when executed by a computer, causes the computer to execute a method of deploying sensors by a robot in a geographical region, the method comprising:

receiving from a server, a first instruction including information corresponding to the geographical region, the information including at least a plurality of boundary locations of the geographical region and a first coordinate of the geographical region corresponding to a starting location for sensor deployment;

receiving from the server, a second instruction indicating one of a first manner and a second manner of deploying sensors in the geographical region;

computing based on the second instruction, a path to traverse the geographical region in a plurality of steps, each step of the plurality of steps having a predetermined magnitude, the traversing being performed until one of a first stopping criteria corresponding to the first manner of deploying sensors and a second stopping criteria corresponding to the second manner of deploying sensors being satisfied;

deploying sensors in the geographical region at each traversed step size;

receiving from each deployed sensor, information indicating absence of sensors in a neighboring area of the deployed sensor;

repeating the traversing and deploying of sensors in the neighboring area based on the received information until all corners of the geographical region have been visited at least once, and

checking for any available empty neighboring area, wherein checking for any available empty neighboring area includes

receiving, from one or more of the sensors, empty neighboring area information from the sensor adjacent to the empty neighboring area, the empty neighboring area information including a first location corresponding to the sensor adjacent to the empty neighboring area, ID of the sensor adjacent to the empty neighboring area, and a second location corresponding to the empty neighboring area, and

deploying sensors, wherein deploying sensors starts from the first location received from the sensor adjacent to the empty neighboring area,

wherein a total distance traversed by the robot in the first manner of deploying sensors is 2n*(m+1)/l+m, wherein m is a width of the geographical region, n is a length of the geographical region, and l is a sensing range of the sensor,

wherein the robot traces its path backwards to its last known starting point and further adds an offset as a step size for the robot to proceed when the robot encounters an obstacle or boundary of the geographical region.

12. The non-transitory computer readable medium of claim 11, wherein the second instruction includes one of the first manner and the second manner of deploying sensors in the geographical region based on an orientation of a plurality of obstacles in the geographical region.

13. The non-transitory computer readable medium of claim 11, the method further comprising:

traversing to the first coordinate of the geographical region based on one of the first stopping criteria and the second stopping criteria being satisfied.

14. The non-transitory computer readable medium of claim 11, wherein the first stopping criteria corresponding to the first manner of deploying sensors is satisfied upon the robot traversing each corner of the geographical region at least once and wherein the second stopping criteria corresponding to the second manner of deploying sensors is satisfied upon the robot traversing each corner of the geographical region exactly once.

15. The non-transitory computer readable medium of claim 11, wherein the first manner of deploying sensors in the geographical area further comprising:

traversing by the step size, in an upward direction to a second location;

moving in a right direction from the second location; and

traversing back to the second location based on encountering one of an obstacle and a boundary of the geographical region.

16. The non-transitory computer readable medium of claim 11, wherein the second manner of deploying sensors in the geographical area further comprising:

traversing by the step size in a first direction;

moving in an upward direction based on encountering one of an obstacle and a boundary of the geographical region; and

traversing by the step size in a second direction, the second direction being opposite to the first direction.

17. The non-transitory computer readable medium of claim 11, wherein a total distance traversed by the robot in the second manner of deploying sensors is n*(m+1)/l+m, wherein m is a width of the geographical region, n is a length of the geographical region, and l is a sensing range of the sensor.

18. A sensor deploying device comprising:

circuitry configured to;

receive from a server, a first instruction including information corresponding to the geographical region, the information including at least a plurality of boundary locations of the geographical region and a first coordinate of the geographical region corresponding to a starting location for sensor deployment,

receive from the server, a second instruction indicating one of a first manner and a second manner of deploying sensors in the geographical region,

compute, based on the second instruction, a path to traverse the geographical region in a plurality of steps, each step of the plurality of steps having a predetermined magnitude, the traversing being performed until one of a first stopping criteria corresponding to the first manner of deploying sensors and a second stopping criteria corresponding to the second manner of deploying sensors being satisfied,

deploy sensors in the geographical region at each traversed step size,

receive from each deployed sensor, information indicating absence of sensors in a neighboring area of the deployed sensor,

repeat the traversing and deploying of sensors in the neighboring area based on the received information until all corners of the geographical region have been visited at least once, and

check for any available empty neighboring area, wherein checking for any available empty neighboring area includes

receiving, from one or more of the sensors, empty neighboring area information from the sensor adjacent to the empty neighboring area, the empty neighboring area information including a first location corresponding to the sensor adjacent to the empty neighboring area, ID of the sensor adjacent to the empty neighboring area, and a second location corresponding to the empty neighboring area, and

deploying sensors, wherein deploying sensors starts from the first location received from the sensor adjacent to the empty neighboring area,

wherein a total distance traversed by the robot in the first manner of deploying sensors is 2n*(m+1)/l+m, wherein m is a width of the geographical region, n is a length of the geographical region, and l is a sensing range of the sensor

wherein the robot traces its path backwards to its last known starting point and further adds an offset as a step size for the robot to proceed when the robot encounters an obstacle or boundary of the geographical region.