For humans and robots to effectively communicate using language, robots must be capable of understanding numeric quantities prevalent in instructions, descriptions, and answers. In contrast to Large Language Model-based approaches that handle numeric quantities as arbitrary input tokens, discriminative approaches such as Distributed Correspondence Graphs use an a priori defined symbol space that must be sufficiently expressive to process any statement. For such general inputs, a large, predefined range of integer and/or rational values has significant impact on efficiency that can prohibit interaction at a natural cadence. This paper introduces a generative approach to symbolic representations for Distributed Correspondence Graphs that handle arbitrary numeric quantities expressed through language. This method dynamically constructs the symbolic representation by parsing the input for number values and/or metric units. Corpus-based experiments demonstrate improvements in runtime efficiency and accuracy versus a baseline with an a priori defined symbolic representation.

Efficient grounding of spatiotemporal relationships in language-based interactions remains a significant challenge for human-robot teams. Such relationships are commonly used when objects cannot be uniquely identified by visual features. Recent methods have demonstrated effective symbol grounding using iterative solves of probabilistic graphical models with simulators to predict the future state of the world. A limitation of such approaches is the requirement that inference is performed at each timestep to determine if the meaning of the statement has changed. In this paper we exploit unique features of the Distributed Correspondence Graph that enable more efficient steps of this architecture that improves the efficiency of symbol grounding. In experiments on examples inspired by previous works involving the grounding of spatiotemporal relationships, we observed an improvement in efficiency between 23% and 26% without a loss in accuracy.

For robots to effectively collaborate with human partners, they need to be able to understand what instructions and/or statements mean in the context of their environment. To ground objects in a dynamic world, robots need an understanding of how both spatial and temporal relationships evolve as a function of time in the environment. However, it is computationally intensive to classify, track, and predict the motion of all objects. Approaches based on Language-Guided Temporally Adaptive Perception (LGTAP) utilize information embedded in the instruction to selectively classify objects to construct minimal but sufficiently detailed models of the environment for symbol grounding. Such methods, however, fail when the instruction refers to the future state of the environment as it lacks any notion of whether to and for how long a future prediction is necessary to ground the instruction. This prompts a reformulation of LGTAP that can selectively utilize information from past observations to accurately predict the future state of objects. This paper describes a novel approach for LGTAP for instructions that may refer to the past, present, and/or future state of the environment by closing the loop around symbol grounding and adaptive perception. A detailed analysis of a grounding problem that refers to the future state of the environment, a corpus-based analysis of performance, and a physical demonstration of natural language understanding is presented along with a description of this novel architecture.

To safely traverse non-flat terrain, robots must account for the influence of terrain shape in their planned motions. Terrain-aware motion planners use an estimate of the vehicle roll and pitch as a function of pose, vehicle suspension, and ground elevation map to weigh the cost of edges in the search space. Encoding such information in a traditional two-dimensional cost map is limiting because it is unable to capture the influence of orientation on the roll and pitch estimates from sloped terrain. The research presented herein addresses this problem by encoding kinodynamic information in the edges of a recombinant motion planning search space based on the Efficiently Adaptive State Lattice (EASL). This approach, which we describe as a Kinodynamic Efficiently Adaptive State Lattice (KEASL), differs from the prior representation in two ways. First, this method uses a novel encoding of velocity and acceleration constraints and vehicle direction at expanded nodes in the motion planning graph. Second, this approach describes additional steps for evaluating the roll, pitch, constraints, and velocities associated with poses along each edge during search in a manner that still enables the graph to remain recombinant. Velocities are computed using an iterative bidirectional method using Eulerian integration that more accurately estimates the duration of edges that are subject to terrain-dependent velocity limits. Real-world experiments on a Clearpath Robotics Warthog Unmanned Ground Vehicle were performed in a non-flat, unstructured environment. Results from 2093 planning queries from these experiments showed that KEASL provided a more efficient route than EASL in 83.72% of cases when EASL plans were adjusted to satisfy terrain-dependent velocity constraints. An analysis of relative runtimes and differences between planned routes is additionally presented. These results reinforce the importance of considering kinodynamic constraints for motion planning in non-flat environments and illustrate how such information can be encoded in an adaptive recombinant motion planning search space.

As robots operate alongside humans in shared spaces, such as homes and offices, it is essential to have an effective mechanism for interacting with them. Natural language offers an intuitive interface for communicating with robots, but most of the recent approaches to grounded language understanding reason only in the context of an instantaneous state of the world. Though this allows for interpreting a variety of utterances in the current context of the world, these models fail to interpret utterances which require the knowledge of past dynamics of the world, thereby hindering effective human-robot collaboration in dynamic environments. Constructing a comprehensive model of the world that tracks the dynamics of all objects in the robot's workspace is computationally expensive and difficult to scale with increasingly complex environments. To address this challenge, we propose a learned model of language and perception that facilitates the construction of temporally compact models of dynamic worlds through closed-loop grounding and perception. Our experimental results on the task of grounding referring expressions demonstrate more accurate interpretation of robot instructions in cluttered and dynamic table-top environments without a significant increase in runtime as compared to an open-loop baseline.

The difficulty associated with the coordinated locomotion of legged robots grows quickly as the number of joints increases. Although prior approaches have addressed this problem through sampling-based planners, learning-based techniques have recently been explored as a means to handle such complexity. Among these recent approaches are systems that utilize probabilistic graphical models in order to infer parameters for central pattern generators (CPGs) which enable the path-following locomotion of highly-articulated legged robots through unstructured terrain. This paper presents a novel formulation of a CPG parameter inference-based path-following controller. The new inference process and accompanying CPG formulation enforce oscillator convergence to the limit-cycle specified by the inferred parameters in addition to biasing towards parameters that quickly reach stable-state. This formulation is shown to improve the performance of CPG parameter inference-based path-following control for legged robots across a number of simulated and physical experiments.

Contemporary approaches to grounded language communication accept an utterance and current world representation as input and produce symbols representing the meaning as output. Since modern approaches to language understanding for human-robot interaction use techniques rooted in machine learning, the quality or sensitivity of the solution is often opaque relative to small changes in input. Although it is possible to sample and visualize solutions over a large space of inputs, naïve application of current techniques is often prohibitively expensive for real-time feedback. In this paper we address this problem by reformulating the inference process of Distributed Correspondence Graphs to only recompute subsets of spatially dependent constituent features over a space of sampled environment models. We quantitatively evaluate the speed of inference in physical experiments involving a tabletop robot manipulation scenario. We demonstrate the ability to visualize configurations of the environment where symbol grounding produces consistent solutions in real-time and illustrate how these techniques can be used to identify and repair gaps or inaccuracies in training data.

Robust motion planners for unmanned ground vehicles must minimize risk while obeying vehicle mobility constraints. Algorithms such as the State Lattice (SL) utilize offline computation to generate expressive control sets which form recombinant search spaces, enabling the use of heuristic search to efficiently produce feasible motion plans online. The Adaptive State Lattice (ASL) demonstrated that local optimizations of the continuous states explored by heuristic search can produce lower-cost solutions in less time than more densely sampled unadapted lattices in sufficiently complex environments. However, the computational cost of this online adaptation limits the application of ASL for mobile robot navigation. We present the Efficiently Adaptive State Lattice (EASL), a novel formalism for online discrete ASL adaptation to overcome this limitation. By discretizing the space of states considered during adaptation, EASL limits the set of feasible motions which could arise during search. This permits the precomputation of an approximation of all motions that could be expressed by an ASL. This approximation removes the online trajectory generation component of the ASL while retaining the benefits of lattice adaptation and enables the use of precomputed swaths for evaluating edge costs. Experimental results demonstrate how an EASL-based planner can generate lower-cost paths than a SL-based planner in roughly equal to or less than the same amount of time.

The complexity associated with the control of highly-articulated legged robots scales quickly as the number of joints increases. Traditional approaches to the control of these robots are often impractical for many real-time applications. This work thus presents a novel sampling-based planning approach for highly-articulated robots that utilizes a probabilistic graphical model (PGM) to infer in real-time how to optimally modify goal-driven, locomotive behaviors for use in closed-loop control. Locomotive behaviors are quantified in terms of the parameters associated with a network of neural oscillators, or rather a central pattern generator (CPG). For the first time, we show that the PGM can be used to optimally modulate different behaviors in real-time (i.e., to select of optimal choice of parameter values across the CPG model) in response to changes both in the local environment and in the desired control signal. The PGM is trained offline using a library of optimal behaviors that are generated using a gradient-free optimization framework.

The speed and accuracy with which robots are able to interpret natural language is fundamental to realizing effective human-robot interaction. A great deal of attention has been paid to developing models and approximate inference algorithms that improve the efficiency of language understanding. However, existing methods still attempt to reason over a representation of the environment that is flat and unnecessarily detailed, which limits scalability. An open problem is then to develop methods capable of producing the most compact environment model sufficient for accurate and efficient natural language understanding. We propose a model that leverages environment-related information encoded within instructions to identify the subset of observations and perceptual classifiers necessary to perceive a succinct, instruction-specific environment representation. The framework uses three probabilistic graphical models trained from a corpus of annotated instructions to infer salient scene semantics, perceptual classifiers, and grounded symbols. Experimental results on two robots operating in different environments demonstrate that by exploiting the content and the structure of the instructions, our method learns compact environment representations that significantly improve the efficiency of natural language symbol grounding.

The utility of collaborative manipulators for shared tasks is highly dependent on the speed and accuracy of communication between the human and the robot. The run-time of recently developed probabilistic inference models for situated symbol grounding of natural language instructions depends on the complexity of the representation of the environment in which they reason. As we move towards more complex bi-directional interactions, tasks, and environments, we need intelligent perception models that can selectively infer precise pose, semantics, and affordances of the objects when inferring exhaustively detailed world models is inefficient and prohibits real-time interaction with these robots. In this paper we propose a model of language and perception for the problem of adapting the configuration of the robot perception pipeline for tasks where constructing exhaustively detailed models of the environment is inefficient and inconsequential for symbol grounding. We present experimental results from a synthetic corpus of natural language instructions for robot manipulation in example environments. The results demonstrate that by adapting perception we get significant gains in terms of run-time for perception and situated symbol grounding of the language instructions without a loss in the accuracy of the latter.

Our goal is to develop models that allow a robot to understand or ``ground" natural language instructionsin the context of its world model. Contemporary approaches estimate correspondences between an instruction and possible candidate groundings such as objects, regions and goals for a robot's action. However, these approaches are unable to reason about abstract or hierarchical concepts such as rows, columns and groups that are relevant in a manipulation domain. We introduce a probabilistic model that incorporates an expressive space of abstract spatial concepts as well as notions of cardinality and ordinality. Abstract concepts are introduced as explicit hierarchical symbols correlated with concrete groundings. Crucially, the abstract groundings form a Markov boundary over concrete groundings, effectively de-correlating them from the remaining variables in the graph which reduces the complexity of training and inference in the model. Empirical evaluation demonstrates accurate grounding of abstract concepts embedded in complex natural language instructions commanding a robot manipulator. The proposed inference method leads to significant efficiency gains compared to the baseline, with minimal trade-off in accuracy.

Autonomous mobile robots require motion planning algorithms that match limitations of on-board computing resources to safely navigate complex environments. In situations where near-optimality is preferential to runtime performance, search spaces that optimize their local connectivity to improve the global optimality of generated solutions are desirable. However, not all nodes in the search space benefit equally from optimization which can result in an inefficient use of computational resources and unnecessary increase in runtime. To address this limitation, we propose an approach called the Selectively Adaptive State Lattice which uses a heuristic based on the local environment to selectively perform optimization and obtain a balance between runtime performance and relative optimality. We present a statistical evaluation of local connectivity optimization and global search with the State Lattice, Adaptive State Lattice, and Selectively Adaptive State Lattice algorithms in randomly generated obstacle fields. We further highlight the performance of each method on a Clearpath Robotics TurtleBot2 in a qualitative physical experiment.

Today, there are many examples of humans and robots regularly interacting in a variety of domains, such as manufacturing, coordinated assembly, and rehabilitation. A resulting demand for more generally accessible communication interfaces has motivated several recent independent research efforts focused on providing robotic systems with a robust natural language interface. Natural language interfaces enable intuitive interaction for untrained and non-expert users. However, achieving real-time performance is particularly challenging, yet essential, to enable flexible, efficient communication. The length of the language input directly impacts the run-time performance and quickly becomes a practical issue when the input is a sequence of multiple sentences, or a monologue. In this work, we propose a variant of a contemporary probabilistic graphical model for language understanding that introduces novel segmentation of the input into a sequence of sentences to be labeled in order. We introduce the notion of a continuously updated prior context that retains the meaning of previous sentences as the inference process proceeds. This prior context serves as evidence during future sentence evaluations. We evaluate our model on two natural language corpora, and demonstrate its utility on a Clearpath Husky A200 mobile manipulator and a simulated Rethink Robotics Baxter Robot.

In interactive human-robot path-planning, a capability for expressing the path topology provides a natural mechanism for describing task requirements. We propose a topology-aware RRT∗ algorithm that can explore in parallel any given set of topologies. The topological information used by the algorithm can either be assigned by the human prior to the planning or be selected from the human in posterior path selection. Theoretical analyses and experimental results are given to show that the optimal path of any topology can be found, including a winding topological constraint wherein the robot must circle one or more objects of interest.

Current methods of grounding natural language instructions do not include reactive or temporal components, making these methods unsuitable for instructions describing tasks as sets of conditional instructions. We introduce the Verifiable Distributed Correspondence Graph (V-DCG) model, which enables the validation of natural language instructions by using Linear Temporal Logic (LTL) specifications together with physical world groundings. We demonstrate the V-DCG model on a physical robot and provide examples of the output our system produces for natural language instructions.

Allowing a human to express topological requirements to a robot in language enables untrained users to guide robot movement without requiring the human to understand sophisticated robot algorithms. By using a homotopy class or classes to represent one or more topological requirements, we build a framework that helps a robot understand a human's intent. This paper reviews a homotopic decomposition method that is used to convert any path into a string, which allows homotopic path equivalence to be performed by comparing strings. We then integrate the Homotopic Distributed Correspondence Graph (HoDCG) to infer the homotopic constraint in the format of strings from a language instruction. Finally, we use a homotopic path-planning algorithm that finds the optimal paths for a given objective and homotopic constraint. Experiment results show how a language instruction is converted into a path driven by an implicit topological requirement.

Natural language offers an intuitive and flexible means for humans to communicate with the robots that we will increasingly work alongside in our homes and workplaces. Recent advancements have given rise to robots that are able to interpret natural language manipulation and navigation commands, but these methods require a prior map of the robot's environment. In this paper, we propose a novel learning framework that enables robots to successfully follow natural language route directions without any previous knowledge of the environment. The algorithm utilizes spatial and semantic information that the human conveys through the command to learn a distribution over the metric and semantic properties of spatially extended environments. Our method uses this distribution in place of the latent world model and interprets the natural language instruction as a distribution over the intended behavior. A novel belief space planner reasons directly over the map and behavior distributions to solve for a policy using imitation learning. We evaluate our framework on a voice-commandable wheelchair. The results demonstrate that by learning and performing inference over a latent environment model, the algorithm is able to successfully follow natural language route directions within novel, extended environments.

Natural language interfaces are powerful tools that enables humans and robots to convey information without the need for extensive training or complex graphical interfaces. Statistical techniques that employ probabilistic graphical models have proven effective at interpreting symbols that represent commands and observations for robot direction-following and object manipulation. A limitation of these approaches is their inefficiency in dealing with larger and more complex symbolic representations. Herein, we present a model for language understanding that uses parse trees and environment models both to learn the structure of probabilistic graphical models and to perform inference over this learned structure for symbol grounding. This model, called the Hierarchical Distributed Correspondence Graph (HDCG), exploits information about symbols that are expressed in the corpus to construct minimalist graphical models that are more efficient to search. In a series of comparative experiments, we demonstrate a significant improvement in efficiency without loss in accuracy over contemporary approaches for human-robot interaction.

Natural language interfaces for robot control aspire to find the best sequence of actions that reflect the behavior intended by the instruction. This is difficult because of the diversity of language, variety of environments, and heterogeneity of tasks. Previous work has demonstrated that probabilistic graphical models constructed from the parse structure of natural language can be used to identify motions that most closely resemble verb phrases. Such approaches however quickly succumb to computational bottlenecks imposed by construction and search the space of possible actions. Planning constraints, which define goal regions and separate the admissible and inadmissible states in an environment model, provide an interesting alternative to represent the meaning of verb phrases. In this paper we present a new model called the Distributed Correspondence Graph (DCG) to infer the most likely set of planning constraints from natural language instructions. A trajectory planner then uses these planning constraints to find a sequence of actions that resemble the instruction. Separating the problem of identifying the action encoded by the language into individual steps of planning constraint inference and motion planning enables us to avoid computational costs associated with generation and evaluation of many trajectories. We present experimental results from comparative experiments that demonstrate improvements in efficiency in natural language understanding without loss of accuracy.

The paper describes the system developed by researchers from MIT for the Defense Advanced Research Projects Agency's (DARPA) Virtual Robotics Challenge (VRC), held in June 2013. The VRC was the first competition in the DARPA Robotics Challenge (DRC), a program that aims to “develop ground robotic capabilities to execute complex tasks in dangerous, degraded, human-engineered environments”. The VRC required teams to guide a model of Boston Dynamics' humanoid robot, Atlas, through driving, walking, and manipulation tasks in simulation. Team MIT's user interface, the Viewer, provided the operator with a unified representation of all available information. A 3D rendering of the robot depicted its most recently estimated body state with respect to the surrounding environment, represented by point clouds and texture-mapped meshes as sensed by on-board LIDAR and fused over time.

We present the motion planning framework for an autonomous vehicle navigating through urban environments. Such environments present a number of motion planning challenges, including ultra-reliability, high-speed operation, complex inter-vehicle interaction, parking in large unstructured lots, and constrained maneuvers. Our approach combines a model-predictive trajectory generation algorithm for computing dynamically-feasible actions with two higher-level planners for generating long range plans in both on-road and unstructured areas of the environment. In this Part I of a two-part paper, we describe the underlying trajectory generator and the on-road planning component of this system. We provide examples and results from ldquoBossrdquo, an autonomous SUV that has driven itself over 3000 kilometers and competed in, and won, the Urban Challenge.

We present the motion planning framework for an autonomous vehicle navigating through urban environments. Such environments present a number of motion planning challenges, including ultra-reliability, high-speed operation, complex inter-vehicle interaction, parking in large unstructured lots, and constrained maneuvers. Our approach combines a model-predictive trajectory generation algorithm for computing dynamically-feasible actions with two higher-level planners for generating long range plans in both on-road and unstructured areas of the environment. In this Part II of a two-part paper, we describe the unstructured planning component of this system used for navigating through parking lots and recovering from anomalous on-road scenarios. We provide examples and results from ldquoBossrdquo, an autonomous SUV that has driven itself over 3000 kilometers and competed in, and won, the Urban Challenge.

We present a method for trajectory generation for all-wheel steering mobile robots which can account for rough terrain and predictable vehicle dynamics and apply it to the problem of generating optimal motion splines. There has been little work in trajectory generation for vehicles with all-wheel steering capability compared to the Ackermann, differential-drive, or omnidirectional mobility system models. The presented method linearizes and inverts forward models of propulsion, suspension, and motion to minimize boundary state error given a parameterized set of controls. Our method for generating efficient motion splines between a series of state boundary constraints optimizes the free path heading boundary constraint while meeting position and orientation state constraints. We demonstrate this algorithm on the Rocky 8 rover platform, where parameterized linear velocity, curvature, and path heading controls are generated which satisfy position, orientation, and path heading constraints in rough terrain