For robots to operate in a three dimensional world and interact with humans, learning spatial relationships among objects in the surrounding is necessary. Reasoning about the state of the world requires inputs from many different sensory modalities including vision (V) and haptics (H). We examine the problem of desk organization: learning how humans spatially position different objects on a planar surface according to organizational “preference”. We model this problem by examining how humans position objects given multiple features received from vision and haptic modalities. However, organizational habits vary greatly between people both in structure and adherence. To deal with user organizational preferences, we add an additional modality, “utility” (U), which informs on a particular human's perceived usefulness of a given object. Models were trained as generalized (over many different people) or tailored (per person). We use two types of models: random forests, which focus on precise multi-task classification, and Markov logic networks, which provide an easily interpretable insight into organizational habits. The models were applied to both synthetic data, which proved to be learnable when using fixed organizational constraints, and human-study data, on which the random forest achieved over 90% accuracy. Over all combinations of {H, U, V} modalities, UV and HUV were the most informative for organization. In a follow-up study, we gauged participants preference of desk organizations by a generalized random forest organization vs. by a random model. On average, participants rated the random forest models as 4.15 on a 5-point Likert scale compared to 1.84 for the random model.

Particle Swarm Optimization is an effective algorithm because of the combination of the stochastic behavior of particles and the swarm structure. Unfortunately these features also make it difficult to understand the dynamics of PSO. Common methods of analyzing PSO rely on simplifying the algorithm, e.g., assuming stagnation (a state where the swarm ceases finding better solutions) or treating the stochastic factors as constants. In this paper, we expand on earlier work to understand the dynamics of PSO which used input-to-state stability analysis. In particular, we decompose PSO more completely and use the properties of combinations of input-to-state stable components to model convergence at all levels up to and including the entire swarm. This approach allows us to conceptualize the swam as a leader-follower structure and analyze the swarm under a variety of conditions including various fitness functions.

Asymptotically-optimal motion planners such as RRT* have been shown to incrementally approximate the shortest path between start and goal states. Once an initial solution is found, their performance can be dramatically improved by restricting subsequent samples to regions of the state space that can potentially improve the current solution. When the motion-planning problem lies in a Euclidean space, this region Xinf, called the informed set, can be sampled directly. However, when planning with differential constraints in non-Euclidean state spaces, no analytic solutions exists to sampling Xinfdirectly. State-of-the-art approaches to sampling Xinfin such domains such as Hierarchical Rejection Sampling (HRS) may still be slow in high -dimensional state space. This may cause the planning algorithm to spend most of its time trying to produces samples in Xinfrather than explore it. In this paper, we suggest an alternative approach to produce samples in the informed set Xinffor a wide range of settings. Our main insight is to recast this problem as one of sampling uniformly within the sub-level-set of an implicit non-convex function. This recasting enables us to apply Monte Carlo sampling methods, used very effectively in the Machine Learning and Optimization communities, to solve our problem. We show for a wide range of scenarios that using our sampler can accelerate the convergence rate to high-quality solutions in high-dimensional problems.

In this paper, we introduce a Markov chain Monte Carlo (MCMC)method to solve multi-objective motion-planning problems. We formulate the problem of finding Pareto-optimal trajectories as a problem of sampling trajectories from a Pareto-optimal set. We define an implicit uniform distribution over the Pareto-frontier using a dominance function and then sample in the space of trajectories. The nature of MCMC guarantees the convergence to the Pareto-frontier, while the uniform distribution ensures the diversity of the trajectories. We also propose progressive objective evaluation to increase efficiency in problems with expensive-to-evaluate objective functions. This enables determination of dominance relationship between trajectories before they are entirely evaluated. We finally analyze the effectiveness of the framework and its applications in robotics.

In human-robot collaborative tasks, incorporating qualitative information provided by humans can greatly enhance the robustness and efficacy of robot state estimation. We introduce an algorithmic framework to model qualitative information as quantitative constraints on and between states. Our approach, named Sequentially Constrained Hamiltonian Monte Carlo, integrates Hamiltonian dynamics into Sequentially Constrained Monte Carlo sampling. We are able to generate samples that satisfy arbitrarily complex, non-smooth and discontinuous constraints, which in turn allows us to support a wide range of qualitative information. We evaluate our approach for constrained sampling qualitatively and quantitatively with several classes of constraints. SCHMC significantly outperforms the Metropolis-Hastings algorithm (a standard Markov Chain Monte Carlo (MCMC) method) and the Hamiltonian Monte Carlo (HMC) method, in terms of both the accuracy of the sampling (for satisfying constraints) and the quality of approximation. Compared to Sequentially Constrained Monte Carlo (SCMC), which supports similar kinds of constraints, our SCHMC approach has faster convergence rates and lower parameter sensitivity.

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.

Many fields of study involve decision-making where trade-offs between different desirable outcomes are to be made. This paper introduces four designs for a graphical user interface (GUI) called the Adverb Palette (AP) to support interactive robot path-planning under multiple performance objectives. The GUI designs apply when the robot must go from an initial configuration to a goal configuration while honoring competing objectives. This novel human-robot interface helps the operator issue commands to the robot to take a specific path from the many available paths, thereby helping the user in decision making process. AP is a metaphor that symbolizes an artist's palette where an artist mixes different colors to get a desired shade of color. For the principal GUI designs, each objective is represented as a color. Since we assume that the human specifies the objectives using language, each objective is metaphorically called an adverb. Two of the approaches, the sliders and the waypoints indicator, have been explored by the researchers in the past, and the other two, palette and prism are novel and may be more useful and intuitive.

An important problem in human-robot interaction is for a human to be able to tell the robot go to a particular location with instructions on how to get there or what to avoid on the way. This paper provides a solution to problems where the human wants the robot not only to optimize some objective but also to honor “soft” or “hard” topological constraints, i.e. “go quickly from A to B while avoiding C”. The paper presents the HARRT* (homotopy-aware RRT*) algorithm, which is a computationally scalable algorithm that a robot can use to plan optimal paths subject to the information provided by the human. The paper provides a theoretic justification for the key property of the algorithm, proposes a heuristic for RRT*, and uses a set of simulation case studies of the resulting algorithm to make a case for why these properties are compatible with the requirements of human-robot interactive path-planning.

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.

This paper examines the dynamics of particle swarm optimization (PSO) by modeling PSO as a feedback cascade system and then applying input-to-state stability analysis. Using a feedback cascade system model we can include the effects of the global-best and personal-best values more directly in the model of the dynamics. Thus in contrast to previous study of PSO dynamics, the input-to-state stability property used here allows for the analysis of PSO both before and at stagnation. In addition, the use of input-to-state stability allows this analysis to preserve random terms which were heretofore simplified to constants. This analysis is important because it can inform the setting of PSO parameters and better characterize the nature of PSO as a dynamic system. This work also illuminates the way in which the personal-best and the global-best updates influence the bound on the particle's position and hence, how the algorithm exploits and explores the fitness landscape as a function of the personal best and global best.

One way for a human and a robot to collaborate on a search task is for the human to specify constraints on the robot's path and then allow the robot to find an optimal path subject to these constraints. This paper presents an anytime solution to the robot's path-planning problem when the human specifies a path constraint and an acceptable amount of deviation from this path. The robot's objective is to maximize information gathered during the search subject to this constraint. We first discretize the path constraint and then convert the resulting problem into a multi-partite graph. Information maximization becomes a submodular orienteering problem on this topology structure. Backtracking is used to generate an efficient heuristic for solving this problem, and an expanding tree is used to facilitate an anytime algorithm.