A computing device obtains an incomplete semantic map of a predefined space. The incomplete semantic map includes static landmarks. The computing device receives a set of natural language instructions including a sequence of semantically directive clauses, processes the sequence of semantically directive clauses, decodes 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. In response to the decoding, the computing device inserts a newly identified landmark into the incomplete semantic map.