System and method for determining characteristics of a physical environment with simple motion patterns

• US 8,457,829 B2
• Filed: 02/19/2010
• Issued: 06/04/2013
• Est. Priority Date: 02/19/2010
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Huang, Qingfeng, Zhang, Ying
• Primary Examiner(s): Zimmerman, Brian
• Assistant Examiner(s): EUSTAQUIO, CAL J
• Application Number:
  US12/709,413
• Publication Number:
  US 20110205012A1
• Time in Patent Office: 1,201 Days
• Field of Search: None
• US Class Current: 701/25
• CPC Class Codes: G05D 1/0227 using mechanical sensing means, e.g. for sensing treated area
• CPC Class Codes: G05D 1/0242 using non-visible light signals, e.g. IR or UV signals
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

A system and method for determining characteristics of a physical environment with simple motion patterns are provided. A plurality of raw orientation readings are received from a simple motion pattern. A distribution of possible wall orientations upon each raw reading is determined. Wall direction is determined as the mean value of the distribution.

Claims

1. A system for determining characteristics of a physical environment with simple motion patterns, comprising:

a heading module for receiving a plurality of raw orientation readings from a simple motion pattern comprising at least one of a predetermined motion pattern, a motion pattern selected from a group of patterns based on a physical environment from which the raw orientation readings are received, and a randomly selected motion pattern;

a distribution module for determining a distribution of possible wall orientations upon each raw reading, wherein the distribution is initially a uniform distribution from −

45 to +45 degrees and is sequentially determined upon each of the raw readings according to the equation;

p(θ

_a/θ

_r<sup>−

k+1</sup>)∝

p(θ

_r/θ

_a)·

p(θ

_a/θ

_r<sup>−

k</sup>)

where p(θ

_r/θ

_a) is the probability of reading θ

_r, given an actual angle θ

_a, and k is the k'"'"'th raw wall orientation reading; and

a direction module for determining wall direction as the mean value of the distribution.

2. A system according to claim 1, wherein the simple motion pattern comprises one of rectilinear motion, wall-following motion, and mid-point motion.

3. A system according to claim 1, further comprising:

an odometry module for receiving odometry readings along the simple motion pattern;

a transformation module for transforming the odometry readings to the determined wall direction;

a box module for calculating a bounding box for the transformed odometry readings;

a size module for determining an area size of the physical environment from the bounding box.

4. A system according to claim 1, further comprising:

an odometry module for receiving odometry readings along the simple motion pattern;

an analysis module for analyzing a largest distance between two points from the odometry readings; and

a size module for determining an area size of the physical environment from the largest distance.

5. A system according to claim 4, further comprising:

a pair-wise module determining the pair-wise distance between each of the odometry readings;

a distance module for identifying the largest distance between any of the two odometry readings; and

a dimension module for setting the area size dimension as the largest distance.

6. A system according to claim 1, further comprising:

a touch module for receiving a plurality of touch sensor readings;

a touch order module for analyzing an order of touch sensor readings as same or alternating; and

a type module for determining the type of physical environment from the order.

7. A system according to claim 6, further comprising:

an order identification module for identifying the order as three same sensor readings; and

a characterization module for characterizing the area type as a room.

8. A system according to claim 6, further comprising:

a order identification module for identifying the order as at least two alternate sensor readings; and

a characterization module for characterizing the area type as a hallway.

9. A method for determining characteristics of a physical environment with simple motion patterns, comprising:

receiving a plurality of raw orientation readings from a simple motion pattern comprising at least one of a predetermined motion pattern, a motion pattern selected from a group of patterns based on a physical environment from which the raw orientation readings are received, and a randomly selected motion pattern;

determining a distribution of possible wall orientations upon each raw reading, wherein the distribution is initially a uniform distribution from −

45 to +45 degrees and is sequentially determined upon each of the raw readings according to the equation;

p(θ

_a/θ

_r<sup>−

k+1</sup>)∝

p(θ

_r/θ

_a)·

p(θ

_a/θ

_r<sup>−

k</sup>

where p(θ

_r/θ

_a) is the probability of reading θ

_r, given an actual angle θ

_a, and k is the k'"'"'th raw wall orientation reading; and

determining wall direction as the mean value of the distribution.

10. A method according to claim 9, wherein the simple motion pattern comprises one of rectilinear motion, wall-following motion, and mid-point motion.

11. A method according to claim 9, further comprising:

receiving odometry readings along the simple motion pattern;

transforming the odometry readings to the determined wall direction

calculating a bounding box for the transformed odometry readings; and

determining an area size of the physical environment from the bounding box.

12. A method according to claim 9, further comprising:

receiving odometry readings along the simple motion pattern;

analyzing a largest distance between two points from the odometry readings; and

determining an area size of the physical environment from the largest distance.

13. A method according to claim 12, further comprising:

determining the pair-wise distance between each of the odometry readings;

identifying the largest distance between any of the two odometry readings; and

setting the area size dimension as the largest distance.

14. A method according to claim 9, further comprising:

receiving a plurality of touch sensor readings;

analyzing an order of touch sensor readings as same or alternating; and

determining the type of physical environment from the order.

15. A method according to claim 14, further comprising:

identifying the order as three same sensor readings; and

characterizing the area type as a room.

16. A method according to claim 14, further comprising:

identifying the order as at least two alternate sensor readings; and

characterizing the area type as a hallway.