System and methods for obstacle mapping and navigation

• US 8,712,679 B1
• Filed: 10/28/2011
• Issued: 04/29/2014
• Est. Priority Date: 10/29/2010
• Status: Expired due to Fees

• Current Assignee: UNM Rainforest Innovations (f/k/a STC.UNM) (The University of New Mexico)
• Original Assignee: UNM Rainforest Innovations (f/k/a STC.UNM) (The University of New Mexico)
• Inventors: Sen, Pradeep, Mostofi, Yasamin
• Primary Examiner(s): Badii, Behrang
• Assistant Examiner(s): TESTARDI, DAVID A
• Application Number:
  US13/284,259
• Time in Patent Office: 914 Days
• Field of Search: 701/300, 342/27, 342/191, 342/451, 342/463, 340552-557, 700/248, 700/258
• US Class Current: 701/300
• CPC Class Codes: G01S 13/003 Bistatic radar systems; Multistatic radar systems
• CPC Class Codes: G01S 13/89 for mapping or imaging
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0291 Fleet control monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127
• CPC Class Codes: G09B 29/00 Maps; Plans; Charts; Diagrams, e.g. route diagram star maps G09B27/04; devices for holding or supporting maps A47B97/02; for computing purposes G06G1/14, G09B1/16; display boards G09F

Abstract

A system and methods for building a map non-invasively (i.e. mapping of occluded and non-occluded obstacles) based on a small number of wireless channel measurements. Approaches for building an obstacle map are based on coordinated space, random space and frequency sampling, such that the sparse representation of the map in space, wavelet or spatial variations, are exploited in order to build the map with minimal sensing.

Claims

1. A method of mapping an obstacle within an environment, comprising the steps of:

transmitting wirelessly a plurality of signals from a first robot to a second robot at randomly chosen distances and angles relative to an origin, wherein the first robot and the second robot each include an adaptive directional narrow-beam antenna and do not attempt to have a specific coordinated pattern of movement;

receiving the plurality of signals by the second robot to obtain received signals, wherein portions of the received signals are attenuated by one or more properties of the obstacle;

measuring by the second robot the plurality of received signals to obtain wireless measurements; and

constructing a binary map of pixel values by the second robot from the wireless measurements, wherein the one or more properties of the obstacle is represented by a non-zero pixel value and the absence of the one or more properties of the obstacle is represented by a zero pixel value, the binary map of pixel values representing a map of the environment including the obstacle.

2. The method of mapping an obstacle within an environment according to claim 1, wherein the wireless measurements include at least one of path loss, shadowing, and multipath fading.

3. The method of mapping an obstacle within an environment according to claim 1, wherein the one or more properties of the obstacle is the location of the obstacle.

4. The method of mapping an obstacle within an environment according to claim 1, wherein the non-zero pixel value comprises the wireless decay rate of the received signals within the object.

5. The method of mapping an obstacle within an environment according to claim 1, wherein at least one of the first robot and the second robot further comprises:

a removable electromechanical fixture including a servo motor control mechanism, wherein the removable electromechanical fixture holds the adaptive directional narrow-beam antenna and the servo motor control mechanism rotates the adaptive directional narrow-beam antenna such that it can point at any desired direction.

6. The method of mapping an obstacle within an environment according to claim 1, wherein the wireless measurements are space samples.

7. A system for mapping an obstacle within an environment, comprising:

at least two robot devices, wherein each robot device comprises;

a wireless card;

an adaptive directional narrow-beam antenna configured to transmit and to receive wireless signals;

a removable electromechanical fixture including a servo motor control mechanism, wherein the removable electromechanical fixture holds the adaptive directional narrow-beam antenna and the servo motor control mechanism rotates the adaptive directional narrow-beam antenna such that it can point at any desired direction;

a processor, wherein the processor is configured to perform the following steps;

gathering a plurality of wireless measurements based on the wireless signals at randomly chosen distances and angles relative to an origin while the robot devices do not attempt to have a specific coordinated pattern of movement to obtain gathered wireless measurements, the gathered wireless measurements being random wireless measurements;

reconstructing the environment based on the random wireless measurements; and

creating an obstacle map.

8. The system for mapping an obstacle within an environment according to claim 7, wherein the random wireless measurements are space responses in the space domain.

9. The system for mapping an obstacle within an environment according to claim 7, wherein the reconstructing step considers sparsity in one or more selected from the group comprising of:

space domain, sparsity domain, and space total variation domain.

10. The system for mapping an obstacle within an environment according to claim 7, wherein the reconstructing step utilizes one or more methods selected from the group comprising of:

basis pursuit, matching pursuit, and total variation.

11. The system for mapping an obstacle within an environment according to claim 7, wherein the obstacle map is a 2D slice of a 3D obstacle.

12. The system for mapping an obstacle within an environment according to claim 7, wherein the reconstructing step further comprises the step of applying a threshold to the random wireless measurements.

13. The system for mapping an obstacle within an environment according to claim 12, wherein the threshold value is 10 dB.

14. The system for mapping an obstacle within an environment according to claim 7, wherein the obstacle map is a binary map of pixel values.

15. The system for mapping an obstacle within an environment according to claim 7, wherein the wireless measurements comprise the wireless decay rate of the wireless signal within the object.