TOPOLOGICAL-BASED LOCALIZATION AND NAVIGATION

• US 20100312386A1
• Filed: 06/04/2009
• Published: 12/09/2010
• Est. Priority Date: 06/04/2009
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shani, Guy, Chrysanthakopoulos, Georgios
• Application Number:
  US12/477,915
• Publication Number:
  US 20100312386A1
• Time in Patent Office: Days
• US Class Current: 700/246
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06F 18/257 Belief theory, e.g. Dempster-Shafer
• CPC Class Codes: G06F 18/259 Fusion by voting
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 10/809 of classification results, e.g. where the classifiers operate on the same input data
• CPC Class Codes: G06V 10/814 using belief theory, e.g. Dempster-Shafer
• CPC Class Codes: G06V 10/85 Markov-related models; Markov random fields

Abstract

Functionality is described for probabilistically determining the location of an agent within an environment. The functionality performs this task using a topological representation of the environment provided by a directed graph. Nodes in the directed graph represent locations in the environment, while edges represent transition paths between the locations. The functionality also provides a mechanism by which the agent can navigate in the environment based on its probabilistic assessment of location. Such a mechanism can use a high-level control module and a low-level control module. The high-level control module determines an action for the agent to take by considering a plurality of votes associated with different locations in the directed graph. The low-level control module allows the agent to navigate along a selected edge when the high-level control module votes for a navigation action.

Claims

1. A location and navigation module implemented by electrical data processing functionality, 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 belief determination module configured to determine a plurality of probabilistic beliefs that identify an extent to which the agent is associated with different respective locations of a directed graph;

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

a vote selection module configured to select one of the plurality 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, in part, on motion of the agent within the environment, the navigation action advancing the agent along an identified edge in the directed graph.

2. The location and navigation module of claim 1, wherein other actions that can be selected correspond to:

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.

3. The location and navigation module of claim 1, 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.

4. The location and navigation module of claim 3, wherein the vote determination module is configured to generate a vote for a particular location also based on a cost associated with the relation.

5. The location and navigation module of claim 1, wherein the vote determination module is configured to generate a vote that directs the agent to perform a multi-hop navigation action in response to comparison between a set of probabilistic beliefs associated with at least one location that is directly linked to a destination location, and a set of probabilistic beliefs associated with at least one location that is indirectly linked to the destination location.

6. The location and navigation module of claim 1, wherein the vote determination module is configured to generate a vote that directs the agent to perform an explore action upon determining that the agent has entered a stuck state, the stuck state being associated with a failure of the agent to make progress toward a destination location.

7. A computer readable medium for storing computer readable instructions, the computer readable instructions providing a location and navigation module when executed by one or more processing devices, the computer readable instructions comprising:

logic configured to receive at least one input image provided by an agent within an environment;

logic configured to compare said at least one input image with a plurality of edge images associated with an edge within a directed graph to produce observations, the edge connecting two nodes in the directed graph and corresponding to a transition path between two locations within the environment; and

logic configured to generate a plurality of probabilistic beliefs for a plurality of respective edge images associated with the edge based on the observations, each probabilistic belief corresponding to a likelihood that the agent is associated with an edge image associated with the edge;

logic configured to provide control instructions which control motion of the agent along the edge based on the probabilistic beliefs.

8. The computer readable medium of claim 7, the computer readable instructions further comprising:

logic configured to use the plurality of probabilistic beliefs to identify a matching edge image that is deemed a most appropriate match for said at least one input image provided by the agent;

logic configured to identify a position of the matching edge image within a sequence of the plurality of edges images associated with the edge; and

logic configured to identify a likely location of the agent along the transition path based on the position.

9. The computer readable medium of claim 7, wherein said logic configured to generate is configured to generate a probabilistic belief for a given edge image by multiplying an observation for the given edge image by a filtering factor that takes into consideration motion of the agent along a transition path associated with the edge.

10. The computer readable medium of claim 7, wherein said logic configured to provide control instructions comprises:

logic configured to determine displacement of at least one feature in said at least one input image from a corresponding at least one feature in at least one of the plurality of edge images, to provide at least one offset,

the control instructions being based on said at least one offset.

11. The computer readable medium of claim 10, wherein said logic configured to determine displacement is configured to determine displacements of a plurality of features in said at least one input image from a correspond plurality of features in the plurality of edge images to provide a plurality of offsets,

wherein said logic configured to provide control instructions further comprises:

logic configured to multiply the plurality of probabilistic beliefs by respective offsets to provide weighted offsets; and

logic configured to combine the weighted offsets to provide a final offset, the control instructions being based on the final offset.

12. A method, using electrical data processing functionality, for identifying a location of an agent, comprising:

receiving a plurality of input images provided by the agent within an environment, including

a front image provided by the agent associated with a visual field in view in front of the agent;

a back image provided by the agent associated with a visual field of view in back of the agent; and

depth-related information provided by the agent that identifies distances between features in the environment and the agent;

comparing at least one of the input images with a collection of graph images associated with a directed graph to produce observations, the directed graph presenting a topological representation of the environment, a first subset of graph images being associated with nodes within the directed graph, and a second subset of graph images being associated with edges between the nodes in the directed graph; and

generating a plurality of probabilistic beliefs for a plurality of respective locations based on the observations, each probabilistic belief corresponding to a likelihood that the agent is associated with a location identified in the directed graph,

13. The method of claim 12, wherein said comparing is operative to select between the front image and the back image based on a determined suitability of the front image and the back image, the suitability of the front image with respect to the back image being based on a determination of whether the agent is at a node location or an edge location.

14. The method of claim 12, wherein said comparing is configured to utilize the depth information as a validity check on comparison results obtained using either the front image or the back image.

15. The method of claim 12, wherein said generating comprises generating a probabilistic belief for a given location by multiplying an observation for the given location by a filtering factor that takes into consideration structure of the environment and an action being performed by the agent.

16. The method of claim 15, further comprising generating the filtering factor by:

multiplying a current probabilistic belief for the given location by transition information, the transition information taking into account the action being performed by the agent and a relationship between a candidate location and the given location, said multiplying producing a weighted current belief;

repeating said multiplying for a plurality of candidate locations to provide a plurality of weighted current beliefs; and

summing the weighted current beliefs to provide the filtering factor.

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

18. The method of claim 12, further comprising using the plurality of probabilistic beliefs to perform navigation within the environment, wherein the navigation within the environment defines a transition path, further comprising updating the directed graph to add a new edge associated with the transition path.

19. The method of claim 18, further comprising modifying transition information based on the navigation, the transition information being used to determine the plurality of probabilistic beliefs.

20. The method of claim 12, further comprising adding a juncture point within the directed graph that partitions at least one edge in the directed graph into two segments.