Apparatus and method for dynamically updating landmarks in a space during execution of natural language instructions

1. A method, comprising:

obtaining, by a computing device, an incomplete semantic map of a predefined space, wherein the incomplete semantic map includes static landmarks;

receiving, by the computing device, a set of natural language instructions including a sequence of semantically directive clauses;

processing, by the computing device, the sequence of semantically directive clauses;

decoding, by the computing device, one of an action and a path in the set of natural language instructions using an optimization process and based on the incomplete semantic map;

responsive to the decoding, inserting, by the computing device, a newly identified landmark into the incomplete semantic map;

executing, by the computing device, the set of natural language instructions along a traveling path;

detecting, by the computing device, the newly identified landmark; and

responsive to the detecting of the newly identified landmark, marking, by the computing device, the newly identified landmark as an identified location.

2. The method of claim 1 , wherein the processing comprises:

parsing the sequence of semantically directive clauses from left-to-right;

identifying clauses in the sequence of semantically directive clauses; and

classifying the clauses.

3. The method of claim 2 , wherein the classifying comprises classifying the clauses as one of direction-following clauses and task execution clauses.

4. The method of claim 1 , wherein the decoding comprises:

identifying one of a known landmark and a known task in the set of natural language instructions;

creating a direction with a known clause in the set of natural language instructions; and

eliminating an unknown clause in the set of natural language instructions from the direction.

5. The method of claim 4 , further comprising:

creating at least one path to execute the known clause;

choosing a best and previously unselected path from the at least one path and selecting a landmark on the best and previously unselected path, wherein the selected landmark is known from the incomplete semantic map;

generating a hypothesis for determining an unknown landmark in an eliminated clause in the set of natural language instructions;

interacting with an operator to identify the unknown landmark in the eliminated clause;

wherein the inserting the newly identified landmark into the incomplete semantic map is responsive to the operator affirming the hypothesis; and

responsive to the operator rejecting the hypothesis, repeating choosing, generating and interacting.

6. The method of claim 5 , wherein the interacting comprises using a natural language query to obtain information from the operator about a relationship between the unknown landmark in the eliminated clause and the selected landmark.

7. The method of claim 1 , wherein the inserting comprises marking the newly identified landmark as associated with a location of a selected landmark.

8. The method of claim 1 , further comprising forming the traveling path with the newly identified landmark in the set of natural language instructions.

9. A computing device, comprising:

memory configured to store non-transitory computer-executable instructions; and

a processor configured to perform a set of functions including:

obtaining an incomplete semantic map of a predefined space, wherein the incomplete semantic map includes static landmarks;

receiving a set of natural language instructions including a sequence of semantically directive clauses;

processing the sequence of semantically directive clauses;

decoding one of an action and a path in the set of natural language instructions using an optimization process and based on the incomplete semantic map;

responsive to the decoding, inserting a newly identified landmark into the incomplete semantic map;

executing the set of natural language instructions along a traveling path;

detecting the newly identified landmark; and

responsive to the detecting of the newly identified landmark, marking the newly identified landmark as an identified location.

10. The computing device of claim 9 , wherein the processor is further configured to:

parse the sequence of semantically directive clauses from left-to-right;

identify clauses in the sequence of semantically directive clauses; and

classify the clauses.

11. The computing device of claim 10 , wherein the classifying comprises classifying the clauses as one of direction-following clauses and task execution clauses.

12. The computing device of claim 9 , wherein the decoding comprises:

identifying one of a known landmark and a known task in the set of natural language instructions;

creating a direction with a known clause in the set of natural language instructions; and

eliminating an unknown clause in the set of natural language instructions from the direction.

13. The computing device of claim 12 , wherein the processor is further configured to:

create at least one path to execute the known clause;

choose a best and previously unselected path from the at least one path and selecting a landmark on the best and previously unselected path, wherein the selected landmark is known from the incomplete semantic map;

generate a hypothesis for determining an unknown landmark in an eliminated clause in the set of natural language instructions;

interact with an operator to identify the unknown landmark in the eliminated clause;

wherein the inserting of the newly identified landmark into the incomplete semantic map is responsive to the operator affirming the hypothesis; and

responsive to the operator rejecting the hypothesis, repeat choosing, generating and interacting.

14. The computing device of claim 13 , wherein the interacting comprises using a natural language query to obtain information from the operator about a relationship between the unknown landmark in the eliminated clause and the selected landmark.

15. The computing device of claim 9 , wherein the inserting comprises marking the newly identified landmark as associated with a location of a selected landmark.

16. The computing device of claim 9 , wherein the processor is further configured to form the traveling path with the newly identified landmark in the set of natural language instructions.

17. A method comprising

obtaining, by a computing device, an incomplete semantic map of a predefined space, wherein the incomplete semantic map includes static landmarks;

receiving, by the computing device, a set of natural language instructions including a sequence of semantically directive clauses;

processing, by the computing device, the sequence of semantically directive clauses;

decoding, by the computing device, one of an action and a path in the set of natural language instructions using an optimization process and based on the incomplete semantic map;

identifying, by the computing device, one of a known landmark and a known task in the set of natural language instructions;

creating, by the computing device, a direction with a known clause in the set of natural language instructions;

eliminating, by the computing device, an unknown clause in the set of natural language instructions from the direction;

creating, by the computing device, at least one path to execute the known clause;

choosing, by the computing device, a best and previously unselected path from the at least one path and selecting a landmark on the best and previously unselected path, wherein the selected landmark is known from the incomplete semantic map;

generating, by the computing device, a hypothesis for determining an unknown landmark in an eliminated clause in the set of natural language instructions;

interacting with an operator to identify the unknown landmark in the eliminated clause;

responsive to the operator affirming the hypothesis, inserting a newly identified landmark into the incomplete semantic map; and

responsive to the operator rejecting the hypothesis, repeating choosing, generating and interacting.

18. A computing device comprising:

memory configured to store non-transitory computer-executable instructions; and

a processor configured to perform a set of functions including:

obtaining an incomplete semantic map of a predefined space, wherein the incomplete semantic map includes static landmarks;

receiving a set of natural language instructions including a sequence of semantically directive clauses;

processing the sequence of semantically directive clauses;

decoding one of an action and a path in the set of natural language instructions using an optimization process and based on the incomplete semantic map;

identifying one of a known landmark and a known task in the set of natural language instructions;

creating a direction with a known clause in the set of natural language instructions;

eliminating an unknown clause in the set of natural language instructions from the direction;

creating at least one path to execute the known clause;

choosing a best and previously unselected path from the at least one path and selecting a landmark on the best and previously unselected path, wherein the selected landmark is known from the incomplete semantic map;

generating a hypothesis for determining an unknown landmark in an eliminated clause in the set of natural language instructions;

interacting with an operator to identify the unknown landmark in the eliminated clause;

responsive to the operator affirming the hypothesis, inserting a newly identified landmark into the incomplete semantic map; and

responsive to the operator rejecting the hypothesis, repeating choosing, generating and interacting.