* High resolution videos of talks available by clicking on links in the detailed technical program below. *

Program Overview

Dec 13-16
SIMPAR 2016 in San Francisco

Saturday, Dec 17
SIMPAR and WAFR attendees are invited to join technical tours of robotics labs at UC Berkeley and Stanford University. Tickets are available for transportation between Hotel Vitale, Stanford, and Berkeley for a fee of $70, including lunch. Transportation tickets and the complete tour schedule can be seen by following the link below.

Technical tour schedule and tickets

Sunday, 12/18

8:00-8:30 Registration
8:30-9:45 Session 1
Perception and Localization
9:45-10:45 Plenary: Erik Demaine
10:45-11:15 Coffee Break
11:15-12:30 Session 2
Novel Applications and HRI
12:30-1:30 Lunch
1:30-2:45 Session 3
Sensor-based Tasks
2:45-3:15 Coffee Break
3:15-4:45 Session 4
Planning under Uncertainty
4:45-5:00 Break
5:00-7:00 Reception:
Space Between Gallery

Monday, 12/19

8:30-9:45 Session 5
Dynamics and Locomotion
9:45-10:45 Plenary: Lydia Kavraki
10:45-11:15 Coffee Break
11:15-12:30 Session 6
12:30-1:30 Lunch
1:30-3:00 Session 7
Exact and Approximate Planning
3:00-3:30 Coffee Break
3:30-4:30 Plenary: John Canny
4:30-5:30 Open Problem Session
5:30-5:45 Chairs Remarks
6:00-9:00 Banquet:
Exploratorium Central Gallery

Tuesday, 12/20

8:30-9:45 Session 8
Planning Methods and Tools
9:45-10:45 Plenary: Dan Halperin
10:45-11:15 Coffee Break
11:15-12:30 Session 9
Robot Learning
12:30-1:30 Lunch
1:30-2:45 Session 10
Robust Manipulation and Assembly
2:45-3:15 Coffee Break
3:15-4:45 Session 11
Multi-robot Systems

Keynote Speakers

Erik Demaine

Massachusetts Institute of Technology

Replicators, Transformers, and Robot Swarms: Science Fiction through Geometric Algorithms

Abstract: Science fiction is a great inspiration for science. How can we build reconfigurable robots like Transformers or Terminator 2? How can we build Star Trek-style replicators that duplicate or mass-produce a given shape at the nano scale? How can we orchestrate the motion of a large swarm of robots? Recently we've been exploring possible answers to these questions through computational geometry, in the settings of reconfigurable robots (both modular and folding robots that can become any possible shape), robot swarms (which may be so small and simple that they have no identity), and self-assembly (building computers and replicators out of DNA tiles).

Bio: Erik Demaine is a Professor in Computer Science at the Massachusetts Institute of Technology. Demaine's research interests range throughout algorithms, from data structures for improving web searches to the geometry of understanding how proteins fold to the computational difficulty of playing games. He received a MacArthur Fellowship (2003) as a "computational geometer tackling and solving difficult problems related to folding and bending--moving readily between the theoretical and the playful, with a keen eye to revealing the former in the latter". Erik cowrote a book about the theory of folding, together with Joseph O'Rourke (Geometric Folding Algorithms, 2007), and a book about the computational complexity of games, together with Robert Hearn (Games, Puzzles, and Computation, 2009). Together with his father Martin, his interests span the connections between mathematics and art, including curved origami sculptures in the permanent collections of the Museum of Modern Art in New York, and the Renwick Gallery in the Smithsonian.

Lydia Kavraki

Rice University

20 Years of Sampling Robot Motion

Abstract: Sampling-based planners for robot motion planning were discovered about twenty years ago and have had a major impact in the way we perceive and practice robot planning today. This talk will discuss the advantages and shortcomings of sampling-based planners, and the new challenges that we face when planning for complex robotic systems. The talk will also present advances that robotics-inspired planners have enabled in computational biology and in the design of new therapeutics.

Bio: Lydia Kavraki is the Noah Harding Professor of Computer Science at Rice University. She also holds a joint appointment at the Department of Bioengineering at Rice. Kavraki received her B.A. in Computer Science from the University of Crete in Greece and her Ph.D. in Computer Science from Stanford University working with Jean-Claude Latombe. She splits her research efforts working in robotics and computational structural biology. In robotics she studies task and motion planning, manipulation, and formal methods applied to robotics. In computational structural biology she introduces new methodologies for the analysis of structure and function of molecules from small proteins to viral capsids. Information about Kavraki and her work can be found at www.kavrakilab.org

John Canny

University of California, Berkeley

A Guided Tour of Computer Vision, Robotics, Algebra, and HCI

Abstract: This walk will be a fast, firmly-shepherded tour of work on vision, robotics, algebra and HCI. It will cover several decades of work, and draw connections between earlier work and the state-of-the-art now. Many of these problems were challenges in the definition phase - figuring out the real problem to be solved, and then finding the right methods to solve it. Several of them required digging deeply into other disciplines to discover acctionable principles. In all cases they involved trying new things from the great self-service counter of ideas. Some highlights include mapping high-dimensional sets, moving sets of objects by shaking, flying robots, 3D video and language-learning games. I'll close with recent work on scalable machine learning and deep learning. Much of the work to date in ML and DL is framed as an optimization problem. In ongoing work, we are exploring an alternative framing as Monte-Carlo simulation.

Bio: John Canny is a professor in computer science at UC Berkeley. He is an ACM dissertation award winner, a Packard Fellow, an Okawa Foundation Fellow and currently holds an INRIA International Chair. He works on large-scale machine learning and deep learning. He previously worked in computer vision, robotics, computational geometry, algebra, human-computer interaction and computer-aided learning. Since 2002, he has been developing and deploying behavioral modeling systems in industry. He designed and protyped production systems for Overstock.com, Yahoo, Ebay, and Quantcast, and is currently a visiting scientist at Google.

Dan Halperin

Tel Aviv University

From Piano Movers to Piano Printers: Computing and Using Minkowski Sums

Abstract: The Minkowski sum of two sets P and Q in Euclidean space is the result of adding every point in P to every point in Q. Minkowski sums constitute a fundamental tool in geometric computing, used in a large variety of domains including motion planning, solid modeling, assembly planning, 3d printing and many more. At the same time they are an inexhaustible source of intriguing mathematical and computational problems. We survey results on the structure, complexity, algorithms, and implementation of Minkowski sums in two and three dimensions. We also describe how Minkowski sums are used to solve problems in an array of applications, and primarily in robotics and automation.

Bio: Dan Halperin received his Ph.D. in Computer Science from Tel Aviv University. He then spent three years at the Computer Science Robotics Laboratory at Stanford University. In 1996 he joined the Department of Computer Science at Tel Aviv University, where he is currently a full professor and for two years was the department chair. Halperin's main field of research is Computational Geometry and its Applications. A major focus of his work has been in research and development of robust geometric software, principally as part of the CGAL project and library. The application areas he is interested in include robotics and automated manufacturing, and algorithmic motion planning. Halperin was named an IEEE Fellow in 2015. http://acg.cs.tau.ac.il/danhalperin

Detailed Technical Program

Sunday, Dec. 18

* Best paper award nominee




Session 1: Perception and Localization

Chair: Lauren Miller
8:30 Multiple Start Branch and Prune Filtering Algorithm for Nonconvex Optimization
R Arun Srivatsan and Howie Choset
PDF Video
8:45 Designing Sparse Reliable Pose-Graph SLAM: A Graph-Theoretic Approach
Kasra Khosoussi, Gaurav S. Sukhatme, Shoudong Huang and Gamini Dissanayake
PDF Video Supplement
9:00 Batch Misalignment Calibration of Multiple Three-Axis Sensors
Gabriel Elkaim
PDF Video
9:15 High-Accuracy Preintegration for Visual Inertial Navigation
Kevin Eckenhoff, Patrick Geneva and Guoquan Huang
PDF Video Supplement
9:30 A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group *
David Rosen, Luca Carlone, Afonso Bandeira and John Leonard
PDF Video

Plenary: Erik Demaine

Replicators, Transformers, and Robot Swarms: Science Fiction through Geometric Algorithms Video

Coffee Break


Session 2: Novel Applications and HRI

Chair: Anca Dragan
11:15 Autonomous Visual Rendering Using Physical Motion
Ahalya Prabhakar, Anastasia Mavrommati, Jarvis Schultz and Todd Murphey
PDF Video Supplement
11:30 Cloud-based Motion Plan Computation for Power-Constrained Robots
Jeffrey Ichnowski, Jan Prins and Ron Alterovitz
PDF Video
11:45 Combining System Design and Path Planning
Laurent Denarie, Kevin Molloy, Marc Vaisset, Thierry Simeon and Juan Cortes
PDF Video
12:00 Language-Guided Sampling-based Planning using Temporal Relaxation
Francisco Penedo Alvarez, Cristian-Ioan Vasile and Calin Belta
PDF Video
12:15 Generating Plans that Predict Themselves
Jaime Fisac, Chang Liu, Jessica Hamrick, Shankar Sastry, J. Karl Hedrick, Thomas Griffiths and Anca Dragan
PDF Video



Session 3: Sensor-based Tasks

Chair: Frank van der Stappen
1:30 Sensor-Based Reactive Navigation in Unknown Convex Sphere Worlds *
Omur Arslan and Daniel E. Koditschek
PDF Video Supplement
1:45 You cannot save all the pandas: impossibility results for privacy-preserving tracking
Yulin Zhang and Dylan Shell
PDF Video
2:00 Approximation Algorithms for Tours of Height-varying View Cones
Patrick A Plonski and Volkan Isler
PDF Video
2:15 Competitive Two Team Target Search Game with Communication Symmetry and Asymmetry
Michael Otte, Michael Kuhlman and Donald Sofge
PDF Video Supplement
2:30 Beyond the planning potpourri: reasoning about label transformations on procrustean graphs
Shervin Ghasemlou, Fatemeh Zahra Saberifar, Jason O'Kane and Dylan Shell
PDF Video

Coffee Break


Session 4: Planning Under Uncertainty

Chair: Leslie Kaebling
3:15 Importance Sampling for Online Planning under Uncertainty *
Yuanfu Luo, Haoyu Bai, David Hsu and Wee Sun Lee
PDF Video Supplement
3:30 Reactive Motion Planning in Uncertain Environments via Mutual Information Policies
Ryan MacDonald and Stephen L. Smith
PDF Video
3:45 Linearization in Motion Planning under Uncertainty
Marcus Hoerger, Hanna Kurniawati, Alberto Elfes and Tirthankar Bandyopadhyay
PDF Video Supplement
4:00 Motion Planning for Active Data Association and Localization in Non-Gaussian Belief Spaces
Saurav Agarwal, Amirhossein Tamjidi and Suman Chakravorty
PDF Video Supplement
4:15 Integrated Perception and Control at High Speed: Evaluating Collision Avoidance Maneuvers Without Maps
Peter R. Florence, John Carter and Russ Tedrake
PDF Video
4:30 Risk-Aware Graph Search with Dynamic Edge Cost Discovery
Ryan Skeele, Jen Jen Chung and Geoff Hollinger
PDF Video


Monday, Dec. 19


Session 5: Dynamics and Locomotion

Chair: Joel Burdick
8:30 Symbolic Computation of Dynamics on Manifolds
Brian Bittner and Koushil Sreenath
PDF Video
8:45 A Linear-Time Variational Integrator for Multibody Systems
Jeongseok Lee, C. Karen Liu, Frank C. Park and Siddhartha S. Srinivasa
PDF Video
9:00 A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and Maximum Constraints
Stephen Butler, Mark Moll and Lydia Kavraki
PDF Video
9:15 Dynamic Walking on Stepping Stones with Gait Library and Control Barrier Functions
Quan Nguyen, Xingye Da, Jessy Grizzle and Koushil Sreenath
PDF Video Supplement
9:30 Algorithmic Foundations of Realizing Multi-Contact Locomotion on the Humanoid Robot DURUS
Jacob Reher, Ayonga Hereid, Shishir Kolathaya, Christian Hubicki and Aaron Ames
PDF Video Supplement

Plenary: Lydia Kavraki

20 Years of Sampling Robot Motion

Coffee Break


Session 6: Grasping

Chair: Devin Balkcom
11:15 Synthesis of Energy-Bounded Planar Caging Grasps using Persistent Homology
Jeffrey Mahler, Florian T. Pokorny, Sherdil Niyaz and Ken Goldberg
PDF Video Supplement
11:30 Equilateral Three-Finger Caging of Polygonal Objects Using Contact Space Search *
Hallel A. Bunis, Elon D. Rimon, Thomas F. Allen and Joel W. Burdick
PDF Video Supplement
11:45 On the Distinction between Active and Passive Reaction in Grasp Stability Analysis
Maximilian Haas Heger, Garud Iyengar and Matei Ciocarlie
PDF Video
12:00 Robust Planar Dynamic Pivoting by Regulating Inertial and Gripping Forces
Yifan Hou, Zhenzhong Jia, Aaron Johnson and Matthew Mason
PDF Video Supplement
12:15 Re-configuring knots to simplify manipulation
Weifu Wang and Devin Balkcom
PDF Video Supplement



Session 7: Exact and Approximate Planning

Chair: Lydia Kavraki
1:30 Continuous Pseudoinversion of a Multivariate Function: Application to Global Redundancy Resolution *
Kris Hauser
PDF Video
1:45 A Generalized Label Correcting Method for Optimal Kinodynamic Motion Planning
Brian Paden and Emilio Frazzoli
PDF Video
2:00 Asymptotically optimal planning under piecewise-analytic constraints
William Vega-Brown and Nicholas Roy
PDF Video Supplement
2:15 Decidability of Semi-Holonomic Prehensile Task and Motion Planning
Ashwin Deshpande, Tomas Lozano-Perez and Leslie Kaelbling
PDF Video
2:30 Approximation Algorithms for Time-Window TSP and Prize Collecting TSP Problems
Su Jia, Jie Gao, Joseph Mitchell and Lu Zhao
PDF Video Supplement
2:45 Resolution-Exact Planner for Thick Non-Crossing 2-Link Robots
Chee Yap, Ching-Hsiang Hsu and Zhongdi Luo
PDF Video Supplement

Coffee Break


Plenary: John Canny

A Guided Tour of Computer Vision, Robotics, Algebra, and HCI Video

Open Problem Session

Oren Salzman Video
Russ Tedrake Video
Leslie Kaelbling Video

Chair's Remarks: Ken Goldberg

A Century of Art and Technology in the Bay Area Video


Tuesday, Dec. 20


Session 8: Planning Methods and Tools

Chair: Thierry Simeon
8:30 Fast and Bounded Probabilistic Collision Detection for High-DOF Robots in Dynamic Environments
Chonhyon Park, Jae Sung Park and Dinesh Manocha
PDF Video Supplement
8:45 Efficient nearest neighbor search for dynamical systems with nonholonomic constraints
Valerio Varricchio, Brian Alexander Paden, Dmitry Yershov and Emilio Frazzoli
PDF Video
9:00 Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning
Michal Kleinbort, Oren Salzman and Dan Halperin
PDF Video
9:15 Dynamic Region-biased Rapidly-exploring Random Trees
Jory Denny, Read Sandstrom, Andrew Bregger and Nancy Amato
PDF Video
9:30 Motion Planning for Reconfigurable Mobile Robots Using Hierarchical Fast Marching Trees
William Reid, Robert Fitch, Ali Haydar Goktogan and Salah Sukkarieh
PDF Video Supplement

Plenary: Dan Halperin

From Piano Movers to Piano Printers: Computing and Using Minkowski Sums Video

Coffee Break


Session 9: Robot Learning

Chair: Pieter Abbeel
11:15 SWIRL: A Sequential Windowed Inverse Reinforcement Learning Algorithm for Robot Tasks With Delayed Rewards
Sanjay Krishnan, Animesh Garg, Richard Liaw, Brijen Thananjeyan, Lauren Miller, Florian T. Pokorny, Ken Goldberg
PDF Video
11:30 Adapting Deep Visuomotor Representations with Weak Pairwise Constraints
Eric Tzeng, Coline Devin, Judy Hoffman, Chelsea Finn, Pieter Abbeel, Sergey Levine, Kate Saenko and Trevor Darrell
PDF Video
11:45 Bandit-Based Model Selection for Deformable Object Manipulation
Dale McConachie and Dmitry Berenson
PDF Video Supplement
12:00 Matrix Completion as a Post-Processing Technique for Probabilistic Roadmaps
Joel Esposito and John Wright
PDF Video
12:15 Persistent Surveillance of Events with Unknown Rate Statistics
Cenk Baykal, Guy Rosman, Kyle Kotowick, Mark Donahue and Daniela Rus
PDF Video Supplement



Session 10: Robust Manipulation and Assembly

Chair: Ken Goldberg
1:30 Planning and Resilient Execution of Policies For Manipulation in Contact with Actuation Uncertainty
Calder Phillips-Grafflin and Dmitry Berenson
PDF Video Supplement
1:45 Configuration Lattices for Planar Contact Manipulation Under Uncertainty
Michael C. Koval, David Hsu, Nancy S. Pollard and Siddhartha S. Srinivasa
PDF Video
2:00 On the Effects of Measurement Uncertainty in Optimal Control of Contact Interactions
Brahayam Ponton, Stefan Schaal and Ludovic Righetti
PDF Video Supplement
2:15 Feedback Control of the Pusher-Slider System: A Story of Hybrid and Underactuated Contact Dynamics
Francois Hogan and Alberto Rodriguez
PDF Video
2:30 Assembling and disassembling planar structures with divisible and atomic components
Yinan Zhang, Emily Whiting and Devin Balkcom
PDF Video Supplement

Coffee Break


Session 11: Multi-robot Systems

Chair: Nancy Amato
3:15 A BCMP Network Approach to Modeling and Controlling Autonomous Mobility-on-Demand Systems
Ramon Iglesias, Federico Rossi, Rick Zhang and Marco Pavone
PDF Video Supplement
3:30 Optimal Policies for Platooning and Ride Sharing in Autonomy-Enabled Transportation
Aviv Adler, David Miculescu and Sertac Karaman
PDF Video
3:45 Decentralised Monte Carlo Tree Search for Active Perception
Graeme Best, Oliver Cliff, Timothy Patten, Ramgopal Mettu and Robert Fitch
PDF Video
4:00 Decentralized Multi-Agent Navigation Planning with Braids
Christoforos Mavrogiannis and Ross Knepper
PDF Video
4:15 A Geometric Approach for Multi-Robot Exploration in Orthogonal Polygons
Aravind Preshant Premkumar, Kevin Yu and Pratap Tokekar
PDF Video
4:30 Assignment Algorithms for Variable Robot Formations
Srinivas Akella
PDF Video

* Best paper award nominee

Meals and Social Events


Lunch is scheduled daily from 12:30 to 1:30 PM, and will be provided for all registered attendees. Lunch will be boxed, so we encourage attendees to explore the exhibits throughout the Exploratorium or eat outside along the Embarcadero.

Sunday Reception:

After the technical sessions, WAFR will host an Art Opening in North Beach/Chinatown, a short 15 minute walk from the Exploratorium (see map below). Join us for wine, snacks, and to check out "Robots that Suck," an ongoing project from artist Chris Farris and The Space Between Gallery. Dinner afterward is open: there are many Italian and Chinese restaurants nearby. More information on the Art Opening.


The WAFR banquet will be held in the central gallery of the Exploratorium on Monday night. Buffet-style dinner and drinks will be served. Guests will have the opportunity to check out ongoing exhibits at the Exploratorium during the event. The banquet is included in student and full registrations, and tickets for additional guests can be purchased through the registration site (kids can attend for free!).