Algorithmic Foundations of Robotics XI

We consider the

following

De Berg, Mark

motion-planning problem: we are given

$$m$$

m

unit

Adler, Aviv

discs

in

Solovey, Kiril

a simple polygon with

$$n$$

n

vertices, each at their own start position, and we want to move the discs to a given set of

$$m$$

m

target positions. Contrary to the standard (labeled) version of the problem, each disc is allowed to be moved to any target position, as long as in the end every target position is occupied. We show that this unlabeled version of the problem can be solved in

$$O\left( n\log n+mn+m^2\right) $$

O

n

log

n

+

m

n

+

m

2

time, assuming that the start and target positions are at least some minimal distance from each other. This is in sharp contrast to the standard (labeled) and more general multi-robot motion planning problem for discs moving in a simple polygon, which is known to be strongly

np

-hard.

We

present

Arslan, Omur

a

centralized

Guralnik, Dan P.

online

Koditschek, Daniel E.

(completely reactive) hybrid navigation algorithm for bringing a swarm of

$$n$$

n

perfectly sensed and actuated point particles in Euclidean

$$d$$

d

space (for arbitrary

$$n$$

n

and

$$d$$

d

) to an arbitrary goal configuration with the guarantee of no collisions along the way. Our construction entails a discrete abstraction of configurations using cluster hierarchies, and relies upon two prior recent constructions: (i) a family of hierarchy-preserving control policies and (ii) an abstract discrete dynamical system for navigating through the space of cluster hierarchies. Here, we relate the (combinatorial) topology of hierarchical clusters to the (continuous) topology of configurations by constructing “portals”—open sets of configurations supporting two adjacent hierarchies. The resulting online sequential composition of hierarchy-invariant swarming followed by discrete selection of a hierarchy “closer” to that of the destination along with its continuous instantiation via an appropriate portal configuration yields a computationally effective construction for the desired navigation policy.

This paper

studies

Bayram, Haluk

the

problem

Bozma, Isil

of forming coalitions for dynamic

tasks

Dynamic tasks

in multirobot

systems

Multirobot systems

. As

robots

Cooperative robots

—either individually or in groups—encounter new tasks for which individual or group resources do not suffice, robot coalitions that are collectively capable of meeting these requirements need to be formed. We propose an approach where such tasks are reported to a task coordinator that is responsible for coalition formation. The novelty of this approach is that the process of determining these coalitions is modeled as a coalition formation game where groups of robots are evaluated with respect to resources and cost. As such, the resulting coalitions are ensured so that no group of robots has a viable alternative to staying within their assigned coalition. The newly determined coalitions are then conveyed to the robots which then form the coalitions as instructed. As new tasks are encountered, coalitions merge and split so that the resulting coalitions are capable of doing the newly encountered tasks. Extensive simulations demonstrate the effectiveness of the proposed approach in a wide range of tasks.

This paper

addresses

Charrow, Benjamin

the

Kumar, Vijay

problem

Michael, Nathan

of actively controlling robotic teams with

range-only

Range-only

sensors to (a) discover and (b) localize an unknown number of devices. We develop separate information based objectives to achieve both goals, and examine ways of combining them into a unified approach. Despite the computational complexity of calculating these policies for multiple robots over long time horizons, a series of approximations enable all calculations to be performed in polynomial time. We demonstrate the tangible benefits of our approaches through a series of simulations in complex indoor environments.

Identifying

Chiang, Hao-Tien

collision-free

Lesser, Kendra

trajectories

Malone, Nick

in

environments

Oishi, Meeko

with

Tapia, Lydia

dynamic obstacles is a significant challenge. However, many pertinent problems occur in dynamic environments, e.g., flight coordination, satellite navigation, autonomous driving, and household robotics. Stochastic reachable (SR) sets assure collision-free trajectories with a certain likelihood in dynamic

environments

Dynamic environments

, but are infeasible for multiple moving

obstacles

Moving Obstacles

as the computation scales exponentially in the number of Degrees of Freedom (DoF) of the relative robot-obstacle state space. Other methods, such as artificial potential fields (APF), roadmap-based methods, and tree-based techniques can scale well with the number of obstacles. However, these methods usually have low success rates in environments with a large number of obstacles. In this paper, we propose a method to integrate formal SR sets with ad-hoc APFs for multiple moving obstacles. The success rate of this method is 30 % higher than two related methods for moving obstacle avoidance, a roadmap-based technique that uses a SR bias and an APF technique without a SR bias, reaching over 86 % success in an enclosed space with 100 moving

obstacles

Moving Obstacles

that ricochet off the walls.

This paper

studies

Cornejo, Alejandro

the

problem

Nagpal, Radhika

of having mobile robots in a multi-robot system maintain an estimate of the relative position and relative orientation of near-by robots in the environment. This problem is studied in the context of large

swarms

Swarms

of simple robots which are capable of measuring only the distance to near-by robots. We compare two

distributed

Distributed

localization

Localization

algorithms with different trade-offs between their computational complexity and their coordination requirements. The first algorithm does not require the robots to coordinate their motion. It relies on a non-linear least squares based strategy to allow robots to compute the relative pose of near-by robots. The second algorithm borrows tools from distributed computing theory to coordinate which robots must remain stationary and which robots are allowed to move. This coordination allows the robots to use standard trilateration techniques to compute the relative pose of near-by robots. Both algorithms are analyzed theoretically and validated through simulations.

This paper presents

iris

(Iterative

Deits, Robin

Regional

Tedrake, Russ

Inflation by Semidefinite programming), a new method for quickly computing large polytopic and ellipsoidal regions of obstacle-free space through a series of convex

optimizations

Sequential convex optimization

. These regions can be used, for example, to efficiently optimize an objective over collision-free positions in space for a robot manipulator. The algorithm alternates between two convex optimizations: (1) a quadratic program that generates a set of hyperplanes to separate a convex region of space from the set of obstacles and (2) a semidefinite

program

Semidefinite programming

that finds a maximum-volume ellipsoid inside the polytope intersection of the obstacle-free half-spaces defined by those hyperplanes. Both the hyperplanes and the ellipsoid are refined over several iterations to monotonically increase the volume of the inscribed ellipsoid, resulting in a large polytope and ellipsoid of obstacle-free space. Practical applications of the algorithm are presented in 2D and 3D, and extensions to

$$N$$

N

-dimensional configuration spaces are discussed. Experiments demonstrate that the algorithm has a computation time which is linear in the number of obstacles, and our

matlab

[

18

] implementation converges in seconds for environments with millions of obstacles.

Motion planning

Motion planning

has

Denny, Jory

seen

Julian, Nicole

much

Amato, Nancy

attention

Sandstrom, Read

over the past two decades. A great deal of progress has been made in sampling-based

planning

Sampling-based planning

, whereby a planner builds an approximate representation of the planning space. While these planners have demonstrated success in many scenarios, there are still difficult problems where they lack robustness or efficiency, e.g., certain types of narrow spaces. Conversely, human intuition can often determine an approximate solution to these problems quite effectively, but humans lack the speed and precision necessary to perform the corresponding low-level tasks (such as collision checking) in a timely manner. In this work, we introduce a novel strategy called

Region Steering

in which the user and a PRM planner work

cooperatively

to map the space while maintaining the probabilistic completeness property of the PRM planner. Region Steering utilizes two-way communication to integrate the strengths of both the user and the planner, thereby overcoming the weaknesses inherent to relying on either one alone. In one communication direction, a user can input regions, or bounding volumes in the workspace, to bias sampling towards or away from these areas. In the other direction, the planner displays its progress to the user and colors the regions based on their perceived usefulness. We demonstrate that Region Steering provides roadmap customizability, reduced mapping time, and smaller roadmap sizes compared with fully automated PRMs, e.g., Gaussian PRM.

Sampling-based

Sampling-based path planning

algorithms for

path

Cortés, Juan

planning

Devaurs, Didier

have

Siméon, Thierry

achieved great success during the last 15 years, thanks to their ability to efficiently solve complex high-dimensional problems. However, standard versions of these algorithms cannot guarantee optimality or even high-quality for the produced paths. In recent years, variants of these methods, taking cost criteria into account during the exploration process, have been proposed to compute high-quality paths (such as T-RRT), some even guaranteeing asymptotic optimality (such as RRT*). In this paper, we propose two new sampling-based approaches that combine the underlying principles of RRT* and T-RRT. These algorithms, called T-RRT* and AT-RRT, offer probabilistic completeness and asymptotic optimality guarantees. Results presented on several classes of problems show that they converge faster than RRT* toward the optimal path, especially when the topology of the search space is complex and/or when its dimensionality is high.

To plan

safe

Ferguson, Sarah

trajectories

Grande, Robert

in

How, Jonathan

urban

Luders, Brandon

environments, autonomous

vehicles

Autonomous vehicles

must be able to quickly assess the future intentions of dynamic agents. Pedestrians are particularly challenging to model, as their motion patterns are often uncertain and/or unknown

a priori

. This paper presents a novel changepoint detection and clustering algorithm that, when coupled with offline unsupervised learning of a Gaussian process mixture model (DPGP), enables quick detection of changes in intent and online learning of motion patterns not seen in prior training data. The resulting long-term movement predictions demonstrate improved accuracy relative to offline learning alone, in terms of both intent and trajectory prediction. By embedding these predictions within a chance-constrained motion planner, trajectories which are probabilistically safe to pedestrian motions can be identified in real-time. Hardware experiments demonstrate that this approach can accurately predict motion patterns from onboard sensor/perception data and facilitate robust navigation within a dynamic environment.

Manipulation

problems

Garrett, Caelan

involving

Kaelbling, Leslie

many

Lozano-Perez, Tomas

objects present substantial challenges for motion planning algorithms due to the high dimensionality and multi-modality of the search space. Symbolic task planners can efficiently construct plans involving many entities but cannot incorporate the constraints from geometry and kinematics. In this paper, we show how to extend the heuristic ideas from one of the most successful symbolic planners in recent years, the FastForward (FF) planner, to motion planning, and to compute it efficiently. We use a multi-query roadmap structure that can be conditionalized to model different placements of movable objects. The resulting tightly integrated planner is simple and performs efficiently in a collection of tasks involving

manipulation

Manipulation planning

of many objects.

Nearest

neighbor

Ichnowski, Jeffrey

searching

Nearest neighbor searching

is

a

Alterovitz, Ron

fundamental building block of most sampling-based motion planners. We present a novel method for fast exact nearest neighbor searching in

$$SE(3)$$

S

E

(

3

)

—the 6 dimensional space that represents rotations and translations in 3 dimensions.

$$SE(3)$$

S

E

(

3

)

is commonly used when planning the motions of rigid body robots. Our approach starts by projecting a 4-dimensional cube onto the 3-sphere that is created by the unit quaternion representation of rotations in the rotational group

$${ SO}(3)$$

S

O

(

3

)

. We then use 4 kd-trees to efficiently partition the projected faces (and their negatives). We propose efficient methods to handle the recursion pruning checks that arise with this kd-tree splitting approach, discuss splitting strategies that support dynamic data sets, and extend this approach to

$$SE(3)$$

S

E

(

3

)

by incorporating translations. We integrate our approach into RRT and RRT* and demonstrate the fast performance and efficient scaling of our nearest neighbor search as the tree size increases.

Imagine a

tracking

Klein, Kyle

agent

Suri, Subhash

$$P()$$

P

(

)

who wants to follow a moving target

$$ Q({})$$

Q

(

)

in

$$d$$

d

-dimensional Euclidean space. The tracker has access to a noisy location

sensor

Sensor noise

that reports an estimate

$$\tilde{Q}(t)$$

Q

~

(

t

)

of the target’s true location

$$ Q({t})$$

Q

(

t

)

at time

$$t$$

t

, where

$$|| Q({t}) - \tilde{Q}(t)||$$

|

|

Q

(

t

)

-

Q

~

(

t

)

|

|

represents the sensor’s

localization

Localization

error. We study the limits of

tracking

Tracking

performance under this kind of sensing imprecision. In particular, (1) what is

$$P()$$

P

(

)

’s best strategy to follow

$$ Q({})$$

Q

(

)

if both

$$P()$$

P

(

)

and

$$ Q({})$$

Q

(

)

can move with equal speed, (2) at what rate does the distance

$$|| Q({t}) - P(t) ||$$

|

|

Q

(

t

)

-

P

(

t

)

|

|

grow under worst-case localization noise, (3) if

$$P()$$

P

(

)

wants to keep

$$ Q({})$$

Q

(

)

within a prescribed distance

$$L$$

L

, how much faster does it need to move, and (4) what is the effect of obstacles on the tracking performance, etc. Under a relative error model of noise, we are able to prove upper and lower bounds for the worst-case tracking performance, both with or without obstacles. We also provide simulation results on real and synthetic data to illustrate trackability under imprecise localization.

RRTs are a

popular

Kunz, Tobias

method

Stilman, Mike

for kinodynamic

planning

Kinodynamic planning

that many consider to be probabilistically complete. However, different variations of the RRT algorithm exist and not all of them are probabilistically complete. The tree can be extended using a fixed or variable time step. The input can be chosen randomly or the best input can be chosen such that the new child node is as close as possible to the sampled state according to the used distance metric. It has been shown that for finite input sets an RRT using a fixed step size with a randomly selected input is probabilistically complete. However, this variant is uncommon since it is less efficient. We prove that the most common variant of choosing the best input in combination with a fixed time step is not probabilistically complete.

Motion

vectors

Motion Vector

(MVs)

characterize

Li, Wen

the

movement

Song, Dezhen

of pixel blocks in video streams and are readily available. MVs not only allow us to avoid expensive feature transform and correspondence computations but also provide the motion information for both the environment and moving obstacles. This enables us to develop a new framework that is capable of simultaneous localization, scene mapping, and moving obstacle tracking. This method first extracts planes from MVs and their corresponding pixel macro blocks (MBs) using properties of plane-induced homographies. We then classify MBs as stationary or moving using geometric constraints on MVs. Planes are labeled as part of the stationary scene or moving obstacles using MB voting. Therefore, we can establish planes as observations for extended Kalman filters (EKFs) for both the stationary scene and moving objects. We have implemented the proposed method. The results show that the proposed method can establish plane-based rectilinear scene structure and detect moving objects while achieving similar localization accuracy of 1-Point EKF. More specifically, the system detects moving obstacles at a true positive rate of 96.6 % with a relative absolution trajectory error of no more than 2.53 %.

This

work

Littlefield, Zakary

describes

Bekris, Kostas

STABLE SPARSE RRT

(

SST

), an

algorithm

Li, Yanbo

that (a) provably provides asymptotic (near-)optimality for kinodynamic

planning

Kinodynamic planning

without access to a steering function, (b) maintains only a sparse set of samples, (c) converges fast to high-quality paths and (d) achieves competitive running time to

RRT

, which provides only probabilistic completeness.

SST

addresses the limitation of

RRT

$$^*$$

∗

, which requires a steering function for asymptotic

optimality

Asymptotic optimality

. This issue has motivated recent variations of

RRT

$$^*$$

∗

, which either work for a limiting set of systems or exhibit increased computational cost. This paper provides formal arguments for the properties of the proposed algorithm. To the best of the authors’ knowledge, this is the first sparse data

structure

Sparse data structures

that provides such desirable guarantees for a wide set of systems under a reasonable set of assumptions. Simulations for a variety of benchmarks, including physically simulated ones, confirm the argued properties of the approach.

In contrast to

classic

Lee, Wee Sun

robot

Hsu, David

motion

Lim, Zhan Wei

planning,

informative path planning

(IPP) seeks a path for a robot to sense the world and gain information. In

adaptive

IPP, the robot chooses the next sensing location using all information acquired so far. The goal is to minimize the robot’s travel cost required to identify a true hypothesis. Adaptive IPP is NP-hard. This paper presents

Recursive Adaptive Identification

(RAId), a new polynomial-time approximation algorithm for adaptive IPP. We prove a polylogarithmic approximation bound when the robot travels in a metric space. Furthermore, our experiments suggest that RAId is efficient in practice and provides good approximate solutions for several distinct robot planning tasks. Although RAId is designed primarily for noiseless observations, a simple extension allows it to handle some tasks with noisy observations.

Planning

Knepper, Ross

for

multirobot

Lindzey, Laura

manipulation

Choset, Howie

in

dense

Srinivasa, Siddhartha

clutter

Planning in clutter

becomes particularly challenging as the motion of the manipulated object causes the connectivity of the robots’ free space to change. This paper introduces a data structure, the Feasible Transition Graph (FTG), and

algorithms

Multirobot algorithms

that solve such complex motion planning problems. We define an equivalence relation over object configurations based on the robots’ free space connectivity. Within an equivalence class, the homogeneous multirobot motion planning problem is straightforward, which allows us to decouple the problems of composing feasible object motions and planning paths for individual robots. The FTG captures transitions among the equivalence classes and encodes constraints that must be satisfied for the robots to manipulate the object. From this data structure, we readily derive a complete planner to coordinate such motion. Finally, we show how to construct the FTG in some sample environments and discuss future adaptations to general environments.

Collision prediction

Collision prediction

is a

fundamental

Xi, Zhonghua

operation

Lu, Yanyan

for

planning

Lien, Jyh-Ming

motion in dynamic environment. Existing methods usually exploit complex behavior models or use dynamic constraints in collision prediction. However, these methods all assume simple geometry, such as disc, which significantly limit their applicability. This paper proposes a new approach that advances collision prediction beyond disc robots and handles arbitrary polygons and articulated objects. Our new tool predicts collision by assuming that obstacles are

adversarial

. Comparing to an online motion planner that replans periodically at

fixed time interval

and planner that approximates obstacle with discs, our experimental results provide strong evidences that the new method significantly reduces the number of replans while maintaining higher success rate of finding a valid path. Our

geometric-based

Geometric reasoning

collision prediction method provides a tool to handle highly complex shapes and provides a complimentary approach to those methods that consider behavior and dynamic constraints of objects with simple shapes.

This work

presents

Kavraki, Lydia

a

Lahijanian, Morteza

planning

Luna, Ryan

framework

Moll, Mark

that allows a robot with stochastic action uncertainty to achieve a high-level task given in the form of a temporal logic formula. The objective is to quickly compute a feedback control policy to satisfy the task specification with maximum probability. A top-down framework is proposed that abstracts the motion of a continuous stochastic system to a discrete, bounded-parameter Markov decision process (

bmdp

), and then computes a control policy over the product of the

bmdp

abstraction and a

dfa

representing the temporal logic specification. Analysis of the framework reveals that as the resolution of the

bmdp

abstraction becomes finer, the policy obtained converges to optimal. Simulations show that high-quality policies to satisfy complex temporal logic specifications can be obtained in seconds, orders of magnitude faster than existing methods.

Motion

planning

Chiang, Yi-Jen

is a

major

Lien, Jyh-Ming

topic

Luo, Zhongdi

in

robotics

Yap, Chee

. Divergent paths have been taken by practical roboticists and theoretical motion planners. Our goal is to produce algorithms that are practical and have strong theoretical guarantees. Recently, we have proposed a subdivision approach based on soft

predicates

Soft predicates

Wang, C., Chiang, Y.-J., Yap, C.: On soft predicates in subdivision motion planning. In: 29th ACM Symposium on Computational Geometry (SoCG’13), pp. 349–358 (2013). To appear CGTA, Special Issue for SoCG’13 [

20

], but with a new notion of correctness called

resolution-exactness

. Unlike mos ques for planar link

robots

Link robots

. The technical contributions of this paper are the design of soft predicates for link robots, a novel “T/R splitting method” for subdivision, and feature-based search strategies. The T/R idea is to give primacy to the translational (T) components, and perform splitting of rotational components (R) only at the leaves of a subdivision tree. We implemented our algorithm for a 2-link robot with 4 degrees of freedom (DOFs). Our implementation achieves real-time performance on a variety of nontrivial scenarios. For comparison, our method outperforms sampling-based methods significantly. We extend our 2-link planner to thick link

robots

Link robots

with little impact on performance. Note that there are no known exact

algorithms

Exact algorithms

for thick link robots.

The

optimal

Balkcom, Devin

trajectory

Lyu, Yu-Han

with respect to some metric may require very many switches between controls, or even infinitely many, a phenomenon called

chattering

; this can be problematic for existing motion

planning

Motion planning

algorithms that plan using a finite set of motion primitives. One remedy is to add some penalty for switching between controls. This paper explores the implications of this

switching cost

for optimal trajectories, using rigid bodies in the plane (which have been studied extensively in the cost-free-switch model) as an example system. Blatt’s Indifference Principle (BIP) is used to derive necessary conditions on optimal trajectories;

Lipschitzian optimization

Lipschitzian optimization

techniques together with an A* search yield an algorithm for finding trajectories that can arbitrarily approximate the optimal trajectories.

We consider the

problem

Karaman, Sertac

of

computing

Ma, Fangchang

the maximum-reward motion in a reward field in an online setting. We assume that the robot has a limited perception range, and it discovers the reward field on the fly. We analyze the performance of a simple, practical lattice-based algorithm with respect to the perception range. Our main result is that, with very little perception range, the robot can collect as much reward as if it could see the whole reward field, under certain assumptions. Along the way, we establish novel connections between this class of problems and certain fundamental problems of nonequilibrium statistical

mechanics

Nonequilibrium statistical mechanics

. We demonstrate our results in simulation examples.

This paper

addresses

Mathew, Neil

a

team

Smith, Stephen

of

cooperating

Waslander, Steven

vehicles performing autonomous deliveries in urban environments. The cooperating team comprises two vehicles with complementary capabilities, a truck restricted to travel along a street network, and a quadrotor micro-aerial vehicle of capacity one that can be deployed from the truck to perform deliveries. The problem is formulated as an optimal path

planning

Optimal path planning

problem on a graph and the goal is to find the shortest cooperative route enabling the quadrotor to deliver items at all requested locations. The problem is shown to be NP-hard using a reduction from the Travelling Salesman Problem and an algorithmic solution is proposed using a graph transformation to the Generalized Travelling Salesman Problem, which can be solved using existing methods. Simulation results compare the performance of the presented algorithms and demonstrate examples of delivery route computations over real urban street maps.

This paper

presents

Ames, Aaron

a

methodology

Ma, Wen-Loong

for

the

Nadubettu Yadukumar, Shishir

composition of complex dynamic behaviors in legged robots, and illustrates these concepts to experimentally achieve robotic

dancing

Dancing

. Inspired by principles from dynamic locomotion, we begin by constructing controllers that drive a collection of

virtual constraints

to zero; this creates a low-dimensional representation of the bipedal robot. Given any two poses of the robot, we utilize this low-dimensional representation to connect these poses through a dynamic transition. The end result is a

meta-dynamical system

that describes a series of poses (indexed by the vertices of a graph) together with dynamic transitions (indexed by the edges) connecting these poses. These formalisms are illustrated in the case of dynamic dancing; a collection of ten poses are connected through dynamic transitions obtained via virtual constraints, and transitions through the graph are synchronized with music tempo. The resulting meta-dynamical system is realized experimentally on the bipedal robot AMBER 2 yielding dynamic robotic dancing.

We study

the

Isler, Volkan

lion-and-man

Noori, Narges

game in which a lion (the pursuer) tries to capture a man (the evader). The players have equal speed and they can observe each other at all times. In this paper, we study the game on surfaces of convex terrains. We show that the lion can capture the man in finite number of steps determined by the terrain geometry.

We present

$${\mathrm {RRT^{X}}}$$

RRT

X

, the

Frazzoli, Emilio

first

Otte, Michael

asymptotically

optimal

Asymptotically optimal

sampling-based motion planning algorithm for

real-time

Real-time

navigation in dynamic environments (containing obstacles that unpredictably appear, disappear, and move). Whenever obstacle changes are observed, e.g., by onboard sensors, a graph rewiring

cascade

quickly updates the search-graph and repairs its

shortest-path

Shortest-path

-to-goal subtree. Both graph and tree are built directly in the robot’s state space, respect the kinematics of the robot, and continue to improve during navigation.

$${\mathrm {RRT^{X}}}$$

RRT

X

is also competitive in static environments—where it has the same amortized per iteration runtime as RRT and RRT*

$$\varTheta \left( \log {n}\right) $$

Θ

log

n

and is faster than RRT

#

$$\omega \left( \log ^2{n}\right) $$

ω

log

2

n

. In order to achieve

$$O\left( \log {n}\right) $$

O

log

n

iteration time, each node maintains a set of

$$O\left( \log {n}\right) $$

O

log

n

expected neighbors, and the search graph maintains

$$\epsilon $$

ϵ

-consistency for a predefined

$$\epsilon $$

ϵ

.

Industrial

parts

Davoodi, Mansoor

are

Panahi, Fatemeh

manufactured

Van der Stappen, A. Frank

to tolerances as no production process is capable of delivering perfectly identical parts. It is unacceptable that a plan for a manipulation task that was determined on the basis of a CAD model of a part fails on some manufactured instance of that part, and therefore it is crucial that the admitted shape

variations

Shape variation

are systematically taken into account during the planning of the task. We study the problem of orienting a part with given admitted shape variations by means of

pushing

Pushing

with a single frictionless jaw. We use a very general model for admitted shape variations that only requires that any valid instance must contain a given convex polygon

$$P_I$$

P

I

while it must be contained in another convex polygon

$$P_E$$

P

E

. The problem that we solve is to determine, for a given

$$h$$

h

, the sequence of

$$h$$

h

push actions that puts all valid instances of a part with given shape variation into the smallest possible interval of final orientations. The resulting algorithm runs in

$$O(hn)$$

O

(

h

n

)

time, where

$$n=|P_I|+|P_E|$$

n

=

|

P

I

|

+

|

P

E

|

.

We

present

Manocha, Dinesh

a

novel

Park, Chonhyon

algorithm for smooth and collision-free navigation for multiple human-like robots. Our approach combines reciprocal collision avoidance with kinematic and dynamic stability constraints to compute a non-oscillatory trajectory for each high-DOF robot. We use a multi-level optimization algorithm that combines acceleration-velocity obstacles with trajectory optimization. We highlight our algorithm’s performance in different environments containing multiple human-like robots with tens of DOFs.

Belief space

planning

Abbeel, Pieter

provides

Goldberg, Ken

a

principled

Kahn, Gregory

framework

Laskey, Michael

to

compute

Patil, Sachin

motion

Schulman, John

plans that explicitly gather information from sensing, as necessary, to reduce uncertainty about the robot and the environment. We consider the problem of planning in Gaussian belief spaces, which are parameterized in terms of mean states and covariances describing the uncertainty. In this work, we show that it is possible to compute locally optimal plans without including the covariance in direct trajectory optimization formulations of the problem. As a result, the dimensionality of the problem scales linearly in the state dimension instead of quadratically, as would be the case if we were to include the covariance in the optimization. We accomplish this by taking advantage of recent advances in numerical optimal control that include automatic differentiation and state of the art convex solvers. We show that the running time of each optimization step of the covariance-free trajectory optimization is

$$O(n^3T)$$

O

(

n

3

T

)

, where

$$n$$

n

is the dimension of the state space and

$$T$$

T

is the number of time steps in the trajectory. We present experiments in simulation on a variety of planning problems under

uncertainty

Motion planning under uncertainty

including manipulator planning, estimating unknown model parameters for dynamical systems, and active simultaneous localization and mapping (active SLAM). Our experiments suggest that our method can solve planning problems in

$$100$$

100

dimensional state spaces and obtain computational speedups of

$$400\times $$

400

×

over related trajectory optimization

methods

Trajectory optimization methods

.

A “ribbon” is a

surface

Abbeel, Pieter

traced

Goldberg, Ken

out by

sweeping

Pan, Jia

a

constant

Patil, Sachin

width line segment along a spatial curve. We consider the problem of planning multiple disjoint and collision-free ribbons of finite thickness along curvature and torsion constrained curves in 3D space. This problem is motivated by the need to route multiple smooth channels through a 3D printed structure for a healthcare application and is relevant to other applications such as defining cooling channels inside turbine blades, routing wires and cables, and planning trajectories for formations of aerial vehicles. We show that this problem is equivalent to planning motions for a rigid body, the cross-section of the

ribbon

Ribbons and strips

, along a spatial curve such that the rigid body is oriented along the unit binormal to the curve defined according to the

Frenet-Serret

frame. We present a two stage approach. In the first stage, we use sampling-based rapidly exploring random trees (RRTs) to generate feasible curvature and torsion constrained ribbons. In the second stage, we locally optimize the curvature and torsion along each ribbon using sequential quadratic programming (SQP). We evaluate this approach for a clinically motivated application: planning multiple channels inside 3D printed implants to temporarily insert high-dose radioactive sources to reach and cover tumors for intracavitary brachytherapy treatment. Constraints on the curvature and torsion avoid discontinuities (kinks) in the

ribbons

Ribbons and strips

which would prevent insertion. In our experiments, our approach achieves an improvement of

$$46\,\%$$

46

%

in coverage of tumor volumes as compared to an earlier approach that generates each channel in isolation.

This paper

introduces

Burdick, Joel

a

local

Hudson, Nicolas

motion

planning

Motion Planning

method

for

Shankar, Krishna

robotic systems with manipulating limbs, moving bases (legged or wheeled), and stance stability constraints arising from the presence of gravity. We formulate the problem of selecting local motions as a linearly constrained quadratic program (QP), that can be solved efficiently. The solution to this QP is a tuple of locally optimal joint velocities. By using these velocities to step towards a goal, both a path and an inverse-kinematic solution to the goal are obtained. This formulation can be used directly for real-time control, or as a local motion planner to connect waypoints. This method is particularly useful for high-degree-of-freedom mobile robotic systems, as the QP solution scales well with the number of joints. We also show how a number of practically important geometric constraints (collision avoidance, mechanism self-collision avoidance, gaze direction, etc.) can be readily incorporated into either the constraint or objective parts of the formulation. Additionally, motion of the base, a particular joint, or a particular link can be encouraged/discouraged as desired. We summarize the important kinematic variables of the formulation, including the stance Jacobian, the reach Jacobian, and a center of mass Jacobian. The method is easily extended to provide sparse solutions, where the fewest number of joints are moved, by iteration using Tibshirani’s method to accommodate an

$$l_1$$

l

1

regularizer. The approach is validated and demonstrated on SURROGATE, a mobile robot with a TALON base, a 7 DOF serial-revolute torso, and two 7 DOF modular arms developed at JPL/Caltech.

This paper is

concerned

Rimon, Elon

with

Shnaps, Iddo

on-line coverage of unknown planar environments by a mobile robot of size

$$D$$

operating with a limited energy capacity battery. The battery capacity is represented by the path length

$$L$$

that the robot can travel under a full battery charge. Starting at

$$S$$

, the robot has to cover a planar environment containing unknown obstacles, and return to

$$S$$

upon task completion. During task execution the robot may return to

$$S$$

at any time to recharge its battery. The paper first describes a battery powered off-line coverage methodology, then introduces the BPC (Battery Powered Coverage) algorithm that performs on-line battery powered coverage using position and local obstacle detection sensors. The performance of the BPC algorithm is measured by its competitiveness, determined by measuring its total on-line path length,

$$l$$

, relative to the optimal off-line solution

$$l_{\textit{opt}}$$

. The paper establishes that the BPC algorithm has a competitive performance of

$$l \le \tfrac{L}{D} l_{\textit{opt}}$$

. The paper additionally establishes a universal lower bound of

$$l \ge \log (\tfrac{L}{4 D}) l_{\textit{opt}}$$

over all on-line battery powered coverage algorithms. Execution example illustrates the usefulness of the BPC algorithm.

We present a

sampling-based

Halperin, Dan

framework

Salzman, Oren

for

Solovey, Kiril

multi-robot motion

planning

Motion planning

which combines an implicit representation of a roadmap with a novel approach for pathfinding in geometrically embedded graphs tailored for our setting. Our pathfinding algorithm,

discrete-RRT

(dRRT), is an adaptation of the celebrated RRT algorithm for the discrete case of a graph, and it enables a rapid exploration of the high-dimensional configuration space by carefully walking through an implicit representation of a tensor product of roadmaps for the individual robots. We demonstrate our approach experimentally on scenarios of up to 60 degrees of freedom where our algorithm is faster by a factor of at least ten when compared to existing algorithms that we are aware of.

We

introduce

Alterovitz, Ron

a

novel

Sun, Wen

optimization-based

Van den Berg, Jur

motion

planner

Optimization-based motion planning

, Stochastic Extended LQR (SELQR), which computes a trajectory and associated linear control policy with the objective of minimizing the expected value of a user-defined cost function. SELQR applies to robotic systems that have stochastic non-linear dynamics with motion

uncertainty

Motion planning under uncertainty

modeled by Gaussian distributions that can be state- and control-dependent. In each iteration, SELQR uses a combination of forward and backward value iteration to estimate the cost-to-come and the cost-to-go for each state along a trajectory. SELQR then locally optimizes each state along the trajectory at each iteration to minimize the expected total cost, which results in smoothed states that are used for dynamics linearization and cost function quadratization. SELQR progressively improves the approximation of the expected total cost, resulting in higher quality plans. For applications with imperfect sensing, we extend SELQR to plan in the robot’s belief space. We show that our iterative approach achieves fast and reliable convergence to high-quality plans in multiple simulated scenarios involving a car-like robot, a quadrotor, and a medical steerable needle performing a liver biopsy procedure.

This paper

presents

Kumar, Vijay

a

polynomial

Michael, Nathan

time

Turpin, Matthew

approximation

algorithm

Approximation algorithm

for Multi-Robot Routing. The Multi-Robot Routing problem seeks to plan paths for a team of robots to visit a large number of interchangeable goal locations as quickly as possible. As a result of providing a constant factor bound on the suboptimality of the total distance any robot travels, the total completion time, or makespan, for robots to visit every goal vertex using this plan is no more than 5 times the optimal completion time. This result is significant because it provides a rigorous guarantee on time optimality, important in applications in which teams of robots carry out time-critical missions. These applications include autonomous exploration, surveillance, first response, and search and rescue.

This paper

considers

Laumond, Jean-Paul

the

Mishra, Bud

problem

Vendittelli, Marilena

of planning collision-free motion of three disks in the plane. One of the three disks, the robot, can autonomously translate in the plane, the other two move only when in contact with the robot. This represents the abstract formulation of a manipulation

planning

Manipulation planning

problem. Despite the simplicity of the formulation, the

decidability

Decidability

of the problem had remained unproven so far. We prove that the problem is decidable, i.e., there exists an exact algorithm that decides whether a solution exists in finite time.

We study the

topology

Baryshnikov, Yuliy

of

the

Chen, Cheng

space

of

Wang, Han

coverings

Covering configuration space

for a metric

tree

Metric tree

with disks embedded in the tree. Focusing on the coverings with excess one disk, we prove that its topological structure is that of a

Cayley graph

Cayley graph

of the permutation group

$$S_{n}$$

S

n

. What follows is a centralized algorithm for stabilizing periodic swarm coverings based upon feedback control with the designed vector field on a maximal subset of the space, removing discontinuity loci.

This paper

presents

Balkcom, Devin

a

controlled

Bell, Matthew

tying

approach

Wang, Weifu

for knots using fixtures and simple pulling motions applied to the ends of string. Each

fixture

Fixture

is specific to a particular knot; the paper gives a design process that allows a suitable

fixture

Fixture

to be designed for an input knot. Knot tying is separated into two phases. In the first phase, a fixture is used to loosely arrange the string around a set of rods, with the required topology of the given knot. In the second phase, the string is pulled taut and slid along the rods (the tightening

fixture

Fixture

) in a direction such that the cross-sections of the rods get closer together, allowing controlled tightening. Successful tying is shown for two interesting cases: a “double coin” knot design, and the top of a shoelace knot.

The first

asymptotically

Frazzoli, Emilio

optimal

Yershov, Dmitry

feedback motion planning algorithm is presented. Our algorithm is based on two well-established numerical practices: (1) the Fast Marching Method

(FMM)

Fast marching method

, which is a numerical Hamilton-Jacobi-Bellman solver, and (2) the adaptive mesh

refinement

Adaptive mesh refinement

algorithm designed to improve the resolution of a simplicial mesh and, consequently, reduce the numerical error. Using the uniform mesh refinement, we show that the resulting sequence of numerical solutions converges to the optimal one. According to the dynamic programming principle, it is sufficient to refine the discretization within a small region around an optimal trajectory in order to reduce the computational cost. Numerical experiments confirm that our algorithm outperforms previous asymptotically optimal

planning

Optimal planning

algorithms, such as PRM* and RRT*, in that it uses fewer discretization points to achieve similar quality approximate optimal paths.

Real-world

applications

Fitch, Robert

of

aerial

Sukkarieh, Salah

robots

Aerial robots

must

Yoo, Chanyeol

consider operational constraints such as fuel level during task

planning

Task planning

. This paper presents an algorithm for automatically synthesizing a continuous non-linear flight controller given a complex temporal logic task specification that can include contingency planning rules. Our method is a hybrid controller where fuel level is treated continuously in the low-level and symbolically in the high-level. The low-level controller assumes the availability of a set of point-estimates of wind velocity and builds a continuous interpolation using Gaussian process regression. Fuel burn and aircraft dynamics are modelled under physically realistic assumptions. Our algorithm is efficient and we show empirically that it is feasible for online execution and replanning. We present simulation examples of navigation in a wind field and surveillance with fuel constraints.

We study the

problem

Rus, Daniela

of

planning

Yu, Jingjin

paths for

$$p$$

p

distinguishable pebbles (robots) residing on the vertices of an

$$n$$

n

-vertex connected graph with

$$p \le n$$

p

≤

n

. A pebble may move from a vertex to an adjacent one in a time step provided that it does not collide with other pebbles. When

$$p = n$$

p

=

n

, the only collision free moves are synchronous rotations of pebbles on disjoint cycles of the graph. We show that the feasibility of such problems is intrinsically determined by the diameter of a (unique) permutation group induced by the underlying graph. Roughly speaking, the diameter of a group

$$\mathbf G$$

G

is the minimum length of the generator product required to reach an arbitrary element of

$$\mathbf G$$

G

from the identity element. Through bounding the diameter of this associated permutation group, which assumes a maximum value of

$$O(n^2)$$

O

(

n

2

)

, we establish a linear time algorithm for deciding the feasibility of such problems and an

$$O(n^3)$$

O

(

n

3

)

algorithm for planning complete paths.