Systems and methods for VSLAM optimization

• US 9,286,810 B2
• Filed: 09/23/2011
• Issued: 03/15/2016
• Est. Priority Date: 09/24/2010
• Status: Active Grant

• Current Assignee: iRobot Corporation
• Original Assignee: iRobot Corporation
• Inventors: Eade, Ethan, Munich, Mario E., Fong, Philip
• Primary Examiner(s): Carter, Aaron W
• Application Number:
  US13/244,221
• Publication Number:
  US 20120121161A1
• Time in Patent Office: 1,635 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0253 extracting relative motion information from a plurality of images taken successively, e.g. visual odometry, optical flow determining position or orientation from images G06T7/70
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/444 Spatial browsing, e.g. 2D maps, 3D or virtual spaces
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G09B 29/007 using computer methods

Abstract

The invention is related to methods and apparatus that use a visual sensor and dead reckoning sensors to process Simultaneous Localization and Mapping (SLAM). These techniques can be used in robot navigation. Advantageously, such visual techniques can be used to autonomously generate and update a map. Unlike with laser rangefinders, the visual techniques are economically practical in a wide range of applications and can be used in relatively dynamic environments, such as environments in which people move. Certain embodiments contemplate improvements to the front-end processing in a SLAM-based system. Particularly, certain of these embodiments contemplate a novel landmark matching process. Certain of these embodiments also contemplate a novel landmark creation process. Certain embodiments contemplate improvements to the back-end processing in a SLAM-based system. Particularly, certain of these embodiments contemplate algorithms for modifying the SLAM graph in real-time to achieve a more efficient structure.

Claims

1. A method for localization and mapping in a system comprising a processor and a camera, wherein the processor is configured to generate a graph with a plurality of pose nodes, a plurality of landmark nodes, and a plurality of edges, wherein:

(i) a pose node comprises a pose of a robot;

(ii) a landmark node comprises a pose of the robot, a landmark identifier corresponding to one or more objects, and an estimate of the location of each of the one or more objects; and

(iii) at least one of the plurality of edges comprises a rigid transformation relating position and orientation of the robot at two locations;

the method comprising;

updating the graph if the number of pose nodes in the graph exceeds a first threshold, comprising;

i) identifying a pose node directly linked to associated Markov blanket nodes with two or more incident edges;

ii) composing said incident edges to generate one or more new edges between pairs of said associated Markov blanket nodes; and

iii) removing the identified pose node and said two or more incident edges;

removing at least one edge of said plurality of edges present in the graph if the total number of edges in the graph exceeds a second threshold; and

updating an estimate of a location of the remaining pose nodes based at least in part on the plurality of edges present in the graph.

2. The method of claim 1, wherein identifying a pose node comprises:

i) for each pose node in the graph, determining a total number of edges that would be present in the graph if the pose node was removed and incident edges composed to generate one or more new edges between pairs of Markov blanket nodes; and

ii) selecting the pose node that would result in the least total number of edges if removed from the graph.

3. The method of claim 1, wherein composing said incident edges comprises:

i) generating an estimate of a relative pose between a pair of Markov blanket nodes, the relative pose estimate being based in part on a vector sum of relative pose measurements associated with two or more incident edges; and

ii) generating a covariance estimate based on covariance estimates associated with the two or more incident edges.

4. The method of claim 1, wherein removing at least one edge of said plurality of edges present in the graph comprises:

i) generating a residual value for each edge in the graph, the residual value being based at least in part on the difference between the relative pose of the nodes connected by the edge in the graph and the relative pose given by the transformation value associated with the same edge;

ii) identifying the edge with lowest residual value; and

iii) removing the identified edge from the graph.

5. The method of claim 1, wherein the system is a mobile robot further comprising a navigation system and a path planner, the method further comprising:

i) generating a set of robot move commands to traverse a trajectory; and

ii) after updating the estimate of the location of the pose nodes present in the graph, updating the set of move commands for navigating the robot based at least in part on the trajectory and updated estimate of the location of the pose nodes present in the graph and a plurality of landmark pose nodes.

6. The method of claim 5, further comprising:

capturing at least one image while traversing the trajectory;

determining whether the one or more images depict a known landmark or a new landmark;

updating the graph, wherein updating the graph comprises;

i) generating a new pose node if the at least one image depicts a known landmark

ii) generating a new landmark pose node if the at least one image depicts a new landmark; and

iii) generating at least one new edge associating the new pose node or new landmark pose node with one or more existing nodes in the graph.

7. The method of claim 6, further comprising extracting a plurality of features, each feature comprising a scale-invariant feature transform (SIFT) feature.

8. The method of claim 1, wherein composing said incident edges to generate one or more new edges between pairs of said associated Markov blanket nodes further comprises:

i) combining at least one of said new edges with an existing edge by generating a weighted average of a mean of the new edge and a mean of the existing edge, and generating a new covariance estimate based on the sum of the inverse of the covariance estimate of the new edge and the covariance estimate of the existing edge.

9. A mobile electronic device comprising:

a camera configured to capture an image;

at least one processor for executing sets of instructions;

memory containing a navigation application;

wherein execution of the navigation application by at least one processor directs the processor to;

maintain a graph comprising a plurality of pose nodes, a plurality of landmark nodes, and edges,

wherein;

(i) a pose node comprises a pose of a robot;

(ii) a landmark node comprises a pose of the robot, a landmark identifier corresponding to one or more objects, and an estimate of the location of each of the one or more objects; and

(iii) an edge comprises a rigid transformation relating position and orientation of the robot at two locations;

update the graph if the number of pose nodes in the graph exceeds a first threshold, comprising;

i) identifying a pose node directly linked to associated Markov blanket nodes with two or more incident edges;

ii) composing said incident edges to generate one or more new edges between pairs of said associated Markov blanket nodes; and

iii) removing the identified pose node and said two or more incident edges;

remove at least one edge of said plurality of edges present in the graph if the total number of edges in the graph exceeds a second threshold; and

update an estimate of a location of each of the remaining pose nodes based at least in part on the plurality of edges present in the graph.

10. The mobile electronic device of claim 9, wherein identifying a pose node comprises:

i) for each pose node in the graph, determining a total number of edges that would be present in the graph if the pose node was removed and incident edges composed to generate one or more new edges between pairs of blanket nodes; and

ii) selecting the pose node that would result in the least total number of edges if removed from the graph.

11. The mobile electronic device of claim 9, wherein composing said incident edges comprises:

i) generating an estimate of a relative pose between a pair of blanket nodes, the relative pose estimate being a vector sum of relative pose measurements associated with two or more incident edges; and

ii) generating a covariance estimate based on covariance estimates associated with the two or more incident edges.

12. The mobile electronic device of claim 9, wherein removing at least one edge of said plurality of edges present in the graph comprises:

i) generating a residual value for each edge in the graph, the residual value being based at least in part on the difference between the relative pose of the nodes connected by the edge in the updated graph and the relative pose given by the mean of the same edge;

ii) identifying the edge with lowest residual value; and

iii) removing the identified edge from the graph.

13. The mobile electronic device of claim 12, wherein the mobile electronic device is a mobile robot further comprising a path planner, the planner further configured to:

i) generate a set of robot move commands to traverse a trajectory; and

ii) after updating the estimate of the location of the remaining pose nodes, updating the set of move commands for navigating the robot based at least in part on the trajectory and updated estimate of the location of the remaining pose nodes.

14. The mobile electronic device of claim 13, wherein execution of the navigation application by at least one processor further directs the processor to:

capture at least one image while traversing the trajectory;

determine whether the one or more images depict a known landmark or a new landmark;

update the graph by;

i) generating a new pose node if the at least one image depicts a known landmark;

ii) generating a new landmark node if the at least one image depicts a new landmark; and

iii) generating at least one new edge associating the new pose node or new landmark node with one or more existing nodes in the graph.

15. The mobile electronic device of claim 14, wherein execution of the navigation application by at least one processor further directs the processor to extract a plurality of features, each feature comprising a scale-invariant feature transform (SIFT) feature.

16. The mobile electronic device of claim 9, wherein composing said incident edges to generate one or more new edges between pairs of said associated blanket nodes further comprises:

i) combining at least one of said new edges with an existing edge by averaging the estimate of a relative pose of the new edge and existing edge, and averaging the covariance estimate of the new edge and existing edge.

17. A method for localization and mapping in a system comprising a processor and a camera, wherein the processor is configured to generate a graph with a plurality of pose nodes and a plurality of edges, the method comprising:

updating the graph if the number of pose nodes in the graph exceeds a first threshold, comprising;

i) identifying a pose node directly linked to associated Markov blanket nodes with two or more incident edges;

ii) composing said incident edges to generate one or more new edges between pairs of said associated Markov blanket nodes; and

iii) removing the identified pose node and said two or more incident edges;

removing at least one edge of said plurality of edges present in the graph if the total number of edges in the graph exceeds a second threshold, comprising;

(i) generating a residual value for each edge in the graph, the residual value being based at least in part on the difference between the relative pose of the nodes connected by the edge in the graph and the relative pose given by the transformation value associated with the same edge;

(ii) identifying the edge with lowest residual value; and

(iii) removing the identified edge from the graph;

updating an estimate of a location of the remaining pose nodes based at least in part on the plurality of edges present in the graph.

18. A mobile electronic device comprising:

a camera configured to capture an image;

at least one processor for executing sets of instructions;

memory containing a navigation application;

wherein execution of the navigation application by at least one processor directs the processor to;

maintain a graph comprising a plurality of pose nodes and edges;

update the graph if the number of pose nodes in the graph exceeds a first threshold, comprising;

i) identifying a pose node directly linked to associated Markov blanket nodes with two or more incident edges;

ii) composing said incident edges to generate one or more new edges between pairs of said associated Markov blanket nodes; and

iii) removing the identified pose node and said two or more incident edges;

remove at least one edge of said plurality of edges present in the graph if the total number of edges in the graph exceeds a second threshold, comprising;

(i) generating a residual value for each edge in the graph, the residual value being based at least in part on the difference between the relative pose of the nodes connected by the edge in the updated graph and the relative pose given by the mean of the same edge;

(ii) identifying the edge with lowest residual value; and

(iii) removing the identified edge from the graph;

update an estimate of a location of each of the remaining pose nodes based at least in part on the plurality of edges present in the graph.