System And Method For Real-Time Mapping Of An Indoor Environment Using Mobile Robots With Limited Sensing

• US 20120195491A1
• Filed: 07/21/2010
• Published: 08/02/2012
• Est. Priority Date: 07/21/2010
• Status: Abandoned Application

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Zhang, Ying, Liu, Juan, Hoffmann, Gabriel
• Application Number:
  US12/841,065
• Publication Number:
  US 20120195491A1
• Time in Patent Office: Days
• US Class Current: 382/153
• CPC Class Codes: G05D 1/0227 using mechanical sensing means, e.g. for sensing treated area
• 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 real-time mapping of an indoor environment using mobile robots with limited sensing are provided. Raw trajectory data comprising a plurality of trajectory points is received from wall-following. Trace segmentation is applied to the raw trajectory data to generate line segments. The line segments are rectified to one another. A map is generated from the rectified line segments.

Claims

1. A system for real-time mapping of an indoor environment using mobile robots with limited sensing, comprising:

raw trajectory data comprising a plurality of trajectory points from wall-following;

a segmentation module applying trace segmentation to the raw trajectory data to generate line segments;

a rectification module rectifying the line segments to one another; and

a map module generating a map from the rectified line segments.

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

a line segment module generating an initial line segment with two of the trajectory points and extending the line segment through each of the next trajectory points until a turn is detected.

3. A system according to claim 2, wherein the turn is detected through a change in one of a bump sensor state, a wall sensor state, and odometry.

4. A system according to claim 1, wherein a current line segment is rectified using a history horizon of the current line segment.

5. A system according to claim 4, wherein the history horizon is a neighborhood of line segments within a distance of the current line segment.

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

a constraint module applying a constraint so any two neighboring line segments are one of aligned or rectilinear to one another.

7. A system according to claim 1, wherein the line segments are rectified according to the equation:

p(s_i+1| z_i+1)∝

·

p_o(z_i+1|s_i+1)·

∫

_sp_d(s_i+1|s_i)·

p(s_i| z_i)ds_i

where p is probability of a rectified sequence given the sequence of measurements, s is state, in this case, orientation of a segment, z is observation, including both odometry and sensor observations, p(s_i+1| z_i+1) is computed from the belief p(s_i| z_i) from the previous time, i, at each step, z_i+1 is observation, p_o(z_i+1|s_i+1), p_o(z|s) is an observation model, p_d(s_i+1|s_i) is a dynamics model, ? is turning angle, where z={?_i, ?<sub>i−

1</sub>, . . . ?<sub>i−

H</sub>}, and H is a history horizon.

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

an orientation module identifying an orientation angle of a current line segment and a history horizon comprising one or more line segments prior to the current line segment; and

a probability module determining a plurality of probabilities of a current direction of the current line segment and each of the line segments of the history horizon and completing the map using the most probable direction for each of the line segments.

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

a loop module identifying a loop within the rectified line segments and closing the loop to generate a closed map.

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

a representation module representing the map as a one-dimensional function;

a loop module detecting a loop comprising overlapping line segment within the map;

an error module adjusting line segment length of the overlapping line segments by an estimated error; and

a closure module closing the loop at the intersection of the adjusted line segments.

11. A method for real-time mapping of an indoor environment using mobile robots with limited sensing, comprising:

receiving raw trajectory data comprising a plurality of trajectory points from wall-following;

applying trace segmentation to the raw trajectory data to generate line segments;

rectifying the line segments to one another; and

generating a map from the rectified line segments.

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

generating an initial line segment with two of the trajectory points; and

extending the line segment through each of the next trajectory points until a turn is detected.

13. A method according to claim 12, wherein the turn is detected through a change in one of a bump sensor state, a wall sensor state, and odometry.

14. A method according to claim 11, further comprising rectifying a current line segment using a history horizon of the current line segment.

15. A method according to claim 14, wherein the history horizon is a neighborhood of line segments within a distance of the current line segment.

16. A method according to claim 11, further comprising applying a constraint so any two neighboring line segments are one of aligned or rectilinear to one another.

17. A method according to claim 11, wherein the line segments are rectified according to the equation:

p(s_i+1| z_i+1)∝

·

p_o(z_i+1|s_i+1)·

∫

_sp_d(s_i+1|s_i)·

p(s_i| z_i)ds_i

where p is probability of a rectified sequence given the sequence of measurements, s is state, in this case, orientation of a segment, z is observation, including both odometry and sensor observations, p(s_i+1| z_i+1) is computed from the belief p(s_i| z_i) from the previous time, i, at each step, z_i+1 is observation, p_o(z_i+1|s_i+1), p_o(z|s) is an observation model, p_d(s_i+1|s_i) is a dynamics model, ? is turning angle, where z={?_i, ?<sub>i−

1</sub>, . . . ?<sub>i−

H</sub>}, and H is a history horizon.

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

identifying an orientation angle of a current line segment and a history horizon comprising one or more line segments prior to the current line segment;

determining a plurality of probabilities of a current direction of the current line segment and each of the line segments of the history horizon;

completing the map using the most probable direction for each of the line segments.

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

identifying a loop within the rectified line segments; and

closing the loop to generate a closed map.

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

representing the map as a one-dimensional function;

detecting a loop comprising overlapping line segment within the map;

adjusting line segment length of the overlapping line segments by an estimated error; and

closing the loop at the intersection of the adjusted line segments.