Quantitative Path-Planning from Qualitative Language Instructions

1 Introduction

Humans and robots think in different ways: humans evaluate qualitatively while robots process quantitative data. For example, a human may say "I am at the east of the building" in expressing a location, while a robot may use a precise coordinate. Similarly a human may specify "run carefully" in requiring a behavior pattern, but a robot may read linear and angular velocities. There is a need to convert between qualitative and quantitative representations for mutual understanding in human-robot interaction. Conversion frommachine data to human-readable form may be possible through visualization and other tools, but it is still somewhat difficult for a robot to understand a human's expression particularly where there is ambiguity.

Understanding qualitative instructions may enable robots to work with untrained human users. We are interested in a robot that plans a path using information specified by a human using natural language; the path may contain multiple criteria and topological requirements. Planning paths from language instructions depends on

• ÷ understanding the qualitative requirement given in a language instruction; and
• ÷ being able to plan paths using preferences over multiple criteria and topological constraints.

Our approach supports a robot to understand human intent in path-planning, which includes (a) a probabilistic model that converts an instruction into a path-planning problem, (b) path-planning algorithms that support multiple objectives and multi-topology constraints. Firstly, a language instruction is grounded into objectives and topology constraints in Section 2. Multiple criteria are supported by multi-objective pathplanning in Section 3, and topology constraints are supported by homotopy-based optimal path-planning in Section 3.

2 Language Understanding for Path-Planning

Understanding the requirement of an instruction, which grounds information according to phrases, guides a corresponding path-planning. The inferred information, objectives and constraints, determines a very best path satisfying the requirement. One efficient tool that models the correspondences between phrases and groundings is DCG (Distributed Correspondence Graph) [Howard et al., 2014], which factorizes the relationship of phrases and groundings by conditional independence assumption. By using DCG, we can infer criteria and topological constraints from verbal instructions.

The semantics of criteria are often associated with adverbs, verbs and environments. For example, "carefully" and "covertly" imply different criteria for movement, also do "walk" and "run". We support the inference of criteria by introducing new types of groundings to a DCG model. Each inferred criterion determines an objective function in an environment, which is used in the optimization of a path-planning problem. We could, moreover, import a speaker's suggestion in generating an objective function, e.g. 'staying away from" indicates high penalty near around some landmark, which indirectly impacts how a resulting path is like. Such an objective function is constructed from continuous correspondence variables in a DCG model. Thus, various objective functions can be inferred for defining path-planning problems from language instructions.

Topological constraints can also be expressed in language, e.g. "go between" and "walk by the left of". Such language sentences indicate spatial relations with landmarks in environment. In a complex sentence, a spatial relation can also be represented as a temporal logic of spatial relations. A spatial relation defines several eligible path topologies. The number of eligible path topologies is determined by the ambiguity of an instruction. The eligible path topologies, which represent the derived topological information from a human's instruction, can be used as a topological constraint in planning.

With high-level human information extracted in the language understanding, we need algorithms to support pathplanning problems with multiple objectives or topological constraints.

3 Multi-Objective Path-Planning

Multiple objectives usually lead to a set of satisfied solutions. When objectives are incomparable or conflicting, the answer to a planning problem becomes a set of Pareto-optimal paths, in which any path is at least better in one objective than any other path. Popular multi-objective optimization methods, e.g. NSGA-II and MOEA-D [Zhang and Li, 2007], cannot be well applied to path-planning problems, because of path shapes and length inconsistency.

Inspired by a decomposition approach MOEA-D [Zhang and Li, 2007], we propose MORRF* (Multi-Objective Rapidly-exploring Random Forrest*) algorithm [Yi et al.,

2015]. In MORRF*, a multi-objective path-planning is decomposed into a set of subproblems, each of which is created by a unique weight vector. Each subproblem is explored by an RRT* for optimality. If we want to find M Pareto-optimal paths in a K-objective path-planning problem, a corresponding MORRF* is consist of two types of RRT* trees [Karaman and Frazzoli, 2011], K reference trees and M subproblem trees. All the trees add the same new sampled position in each iteration. But vertices in trees are connected differently. Each reference tree looks for the optimality of one objective, which supports estimation of Utopia reference vector at each position. By estimated Utopia reference vector and assigned weight vector, each subproblem tree converge to a structure for one subproblem. Combining the solutions of the subproblem trees yields a set of Pareto-optimal paths.

We also propose an interactive interface for assisting human users select a path from a Pareto-optimal set [Meher T. Shaikh and Hoehne, 2016], which efficiently identifies a human's intent by a color-blending process.

4 Homotopy-based Optimal Path-Planning

A topological constraint is defined by multiple eligible path topologies. We choose the homotopy of the paths to distinguish topological difference of paths. When a path can be deformed into another path without encroaching into any obstacle, the two paths are homotopic [Bhattacharya, 2010]. All the feasible paths of a path-planning problem can be categorized into homotopy classes [Bhattacharya, 2010], any of which includes paths that are homotopic. A homotopy class is chosen as a path shape, and several homotopy classes represent a topological constraint. Finding the optimal paths of homotopy classes, which is defined as a homotopy-based optimal path-planning problem, is introduced to find optimal solutions by a topological constraint.

The first step of problem solving depends on a method of identifying the homotopic equivalence of paths. The existing methods can be divided into a homology-approximation approach [Bhattacharya, 2010] and a map-decomposition approach [Hernandez et al., 2015]. We adopt a map-decompose method from [Hernandez et al., 2015], which converts a path into a string representation. A set of reference frames is generated that decompose a given map into subregions. Each reference frame is assigned an ID character. How a path sequentially crosses reference frames can be represented into a string, which is a sequence of ID characters. We propose a homotopic DFA (Deterministic Finite Automata) that converts a path into a string and processes it into a condensed representation. By comparing the condensed strings, the homotopy of corresponding paths can be identified [Yi et al., 2016].

HARRT* (Homotopy-Aware RRT*) [Yi et al., 2016] is proposed that uses a bidirectional RRT* to parallel explore homotopy classes. The homotopic information of each branch is obtained by a homotopic DFA. HARRT* returns the optimal paths of given homotopy classes. To complement its weakness, we propose another RRT*-based algorithm that explores hyperplanes that are created by shapes of homotopy classes. It provides completeness in exploring all possible homotopy classes and also supports winding homotopy classes.

Similar with a multi-objective path-planning problem, a set of solutions for several homotopy classes is obtained in a homotopy-based optimal path-planning problem. The selection of one solution from a set of satisfied paths for a robot can be obtained by an interactive process or a predefined priority rule.

5 FromLanguage to Path

Converting from a qualitative sentence to a quantitative path is being implemented by integrating above components. An instruction sentence is parsed into a semantic structure for creating a corresponding factor graph of DCG. The created factor graph infers objectives and topological constraints, which are used to define a multi-objective or homotopy-based path-planning problem. Solving the path-planning problem returns one or several paths. A prior rule or an interactive process by a human leads to a path for navigation. The framework is being tested with a Turtlebot in an environment with landmarks.