HYBRID-APPROACH FOR LOCALIZATON OF AN AGENT

• US 20120316784A1
• Filed: 06/09/2011
• Published: 12/13/2012
• Est. Priority Date: 06/09/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chrysanthakopoulos, Georgios
• Granted Patent: US 10,088,317 B2
• Time in Patent Office: Days
• US Class Current: 701/519
• CPC Class Codes: B25J 9/1697 Vision controlled systems
• CPC Class Codes: G01C 11/06 by comparison of two or more pictures of the same area
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation

Abstract

Methods and systems for determining the location of an agent within an environment using a hybrid approach are provided. The hybrid approach allows a potentially large physical space to be compressed in the form of a directed graph, in which edges are paths and nodes are locations. An image comparison produces observations for each location and path, which can be used to probabilistically locate the agent in the environment and to select a portion of the 3D point cloud for comparison. The agent can then be localized within the 3D point cloud, or metric-accurate map, using the same features utilized for image matching in the probabilistic location.

Claims

1. A location system, comprising:

a processor configured to implement location modules for an agent, wherein the modules comprise;

a belief determination module configured to determine a probabilistic belief associated with an extent to which the agent is associated with a predicted location on a directed graph; and

a comparison module configured to compare the predicted location with a three dimensional (3D) point cloud to obtain a metric-accurate location for the agent.

2. The location system of claim 1, wherein the predicted location is associated with an image of an environment, and the directed graph comprises a plurality of images collected during a training sequence.

3. The location system of claim 1, wherein the 3D point cloud comprises a list of index values, wherein each index value is a single number representing a feature in a 3D environment.

4. The location system of claim 1, comprising:

a plurality of sensors configured to obtain visual images of the environment, depth images of the environment, or both;

a motion system configured to move the system through the environment in response to the probabilistic belief, the metric-accurate location, or both.

5. The location system of claim 1, comprising:

a high-level control module configured to determine an action to be taken by an agent within an environment based, in part, on structure of the environment, the high-level control module comprising;

a vote determination module configured to generate a plurality of votes associated with each of a plurality of different predicted locations, each vote identifying an action to be taken by the agent, the plurality of votes being weighted, respectively, by a plurality of probabilistic beliefs;

a vote selection module configured to select one of the plurality of votes and an associated action based on the plurality of probabilistic beliefs; and

a low-level control module configured to implement a navigation action selected by the high-level control module based.

6. The location system of claim 5, wherein the navigation action is a direct navigation action in which the agent uses the metric-accurate position to move towards a target destination.

7. The location system of claim 5, wherein the navigation action is an edge hop action in which the agent uses the metric-accurate position to move from an edge in the directed graph to another edge in the directed graph.

8. The location system of claim 5, wherein the navigation action is selected from:

an edge following action in which the agent follows a nearest edge in the directed graph;

an idle action in which the agent takes no action;

a rotate action in which the agent rotates; and

an explore action in which the agent moves throughout an environment without regard to a destination.

9. The location system of claim 5, wherein the vote determination module is configured to generate a vote for a particular location also based on a relation between that location and a destination location.

10. The location system of claim 5, wherein the vote determination module is configured to generate a vote for a particular location also based on a cost associated with the relation.

11. The location system of claim 5, wherein the cost is determined, at least in part, using the metric-accurate location.

12. The location system of claim 1, wherein the processor comprises a remote computational system in communication with the agent.

13. A method for identifying a location of an agent, comprising:

comparing an input image of an environment from a sensor on the agent with a collection of graph images associated with a directed graph to produce an observation, the directed graph representing a topological representation of the environment;

generating a probabilistic belief for a predicted location based, at least in part, on the observation, the probabilistic belief corresponding to a likelihood that the agent is associated with an actual location in the directed graph; and

comparing the predicted location to a portion of a three dimensional (3D) point cloud to determine a metric-accurate location for the agent, wherein the portion is selected based, at least in part, on the probabilistic belief.

14. The method of claim 13, wherein the collection of graph images comprises a first subset of graph images associated with nodes within the directed graph, and a second subset of graph images associated with edges between the nodes in the directed graph.

15. The method of claim 13, comprising generating the directed graph by manually guiding the agent through the environment as the agent takes images within the environment.

16. The method of claim 13, comprising generating the 3D point cloud by:

analyzing a sequence of images from the environment by iteratively performing a pairwise comparison on each two sequential images, wherein the pairwise comparison is performed by;

creating N sets of alternative 3D positions for each feature in a first image, wherein each alternative 3D position comprises a rotation of the feature, a translation of the feature, or both;

creating an index number for each feature in each of the N sets, wherein each index number represents a position in 3D space;

creating an index number for each feature in a next image;

comparing the index number for each feature in the next image to the list of index numbers for each of the N sets, and incrementing a counter when a substantially matching number is found; and

adding the set with the highest value for the counter to the 3D point cloud.

17. The method of claim 13, comprising:

using the metric-accurate location to make a determination that the agent is proximate to an edge in the directed graph, wherein the agent is not currently following the edge; and

using the determination to move the agent to the edge.

18. The method of claim 13, comprising:

using the metric accurate location to determine that two edges are proximate to each other; and

adding a node to the directed graph that connects the two edges.

19. One or more non-volatile computer-readable storage media for storing computer readable instructions, the computer-readable instructions providing a location system when executed by one or more processing devices, the computer-readable instructions comprising:

code configured to receive an input image provided by an agent within an environment;

code configured to compare the input image with a plurality of images associated with a directed graph to produce a probable location for the agent; and

code configured to compare an image associated with the probable location to a three dimensional (3D) point cloud to generate a metric-accurate location, wherein the 3D point cloud comprises a metric map of the environment.

20. The computer readable medium of claim 19, the computer readable instructions further comprising:

logic configured to compare a current metric-accurate location with a target location; and

logic configured to navigate the agent directly towards the target location.