Book Chapters
- . Task and Motion Planning. Encyclopedia of Robotics, Springer Berlin Heidelberg. 2020.
Task and motion planning operates in a combined discrete and continuous space to find a sequence of high-level, discrete actions and corresponding low-level, continuous paths to go from an initial state to a goal state.
@inbook{dantam2020taskmotion, author = {Neil T. Dantam}, editor = {Ang, Marcelo H. and Khatib, Oussama and Siciliano, Bruno}, publisher = {Springer Berlin Heidelberg}, booktitle = {Encyclopedia of Robotics}, title = {\href{http://dx.doi.org/10.1007/978-3-642-41610-1_176-1}{Task and Motion Planning}}, year = {2020} }
Refereed Journal Papers
- . Scaling Infeasibility Proofs via Concurrent, Codimension-one, Locally-updated Coxeter Triangulation. IEEE Robotics and Automation Letters (RA-L). 2023.
Achieving a complete motion planner that guarantees a plan or infeasibility proof in finite time is challenging, especially in high-dimensional spaces. Previous efforts have introduced asymptotically complete motion planners capable of providing a plan or infeasibility proof given long enough time. The algorithm trains a manifold using configuration space samples as data and triangulates the manifold to ensure its existence in the obstacle region of the configuration space. In this paper, we extend the construction of infeasibility proofs to higher dimensions by adapting Coxeter triangulation’s manifold tracing and cell construction procedures to concurrently triangulate the configuration space codimension-one manifold, and we apply a local elastic update to fix the triangulation when part of it is in the free space. We perform experiments on 4-DOF and 5-DOF serial manipulators. Infeasibility proofs in 4D are two orders of magnitude faster than previous results. Infeasibility proofs in 5D complete within minutes.
@article{li2023scaling, author = {Sihui Li and Neil T. Dantam}, journal = {IEEE Robotics and Automation Letters (RA-L)}, title = {\href{http://dx.doi.org/10.1109/LRA.2023.3327655}{Scaling Infeasibility Proofs via Concurrent, Codimension-one, Locally-updated Coxeter Triangulation}}, year = {2023} } - . A Sampling and Learning Framework to Prove Motion Planning Infeasibility. The International Journal of Robotics Research (IJRR). 2023.
We present a learning-based approach to prove infeasibility of kinematic motion planning problems. Sampling-based motion planners are effective in high-dimensional spaces but are only probabilistically complete. Consequently, these planners cannot provide a definite answer if no plan exists, which is important for high-level scenarios, such as task-motion planning. We apply data generated during multi-directional sampling-based planning (such as PRM) to a machine learning approach to construct an infeasibility proof. An infeasibility proof is a closed manifold in the obstacle region of the configuration space that separates the start and goal into disconnected components of the free configuration space. We train the manifold using common machine learning techniques and then triangulate the manifold into a polytope to prove containment in the obstacle region. Under assumptions about the hyper-parameters and robustness of configuration space optimization, the output is either an infeasibility proof or a motion plan in the limit. We demonstrate proof construction for up to 4-DOF configuration spaces. A large part of the algorithm is parallelizable, which offers potential to address higher dimensional configuration spaces.
@article{li2022sampling, author = {Sihui Li and Neil T. Dantam}, journal = {The International Journal of Robotics Research (IJRR)}, title = {\href{http://dx.doi.org/10.1177/02783649231154674}{A Sampling and Learning Framework to Prove Motion Planning Infeasibility}}, year = {2023} } - . Optimizing Non-Markovian Information Gain under Physics-based Communication Constraints. IEEE Robotics and Automation Letters (RA-L). 3. 2021.
In many exploration scenarios, it is important for robots to efficiently explore new areas and constantly communicate results. Mobile robots inherently couple motion and network topology due to the effects of position on wireless propagation, e.g., distance or obstacles between network nodes. Information gain is a useful measure of exploration. However, finding paths that maximize information gain while preserving communication is challenging due to the non-Markovian nature of information gain, discontinuities in network topology, and zero-reward local optima. We address these challenges through an optimization and sampling-based algorithm. Our algorithm scales to 50% more robots and obtains 2-5 times more information relative to path cost compared to baseline planning approaches.
@article{schack2021optimizing, author = {Matthew A. Schack and John G. Rogers and Qi Han and Neil T. Dantam}, number = {3}, volume = {6}, pages = {4813-4819}, journal = {IEEE Robotics and Automation Letters (RA-L)}, title = {\href{http://dx.doi.org/10.1109/LRA.2021.3068935}{Optimizing Non-Markovian Information Gain under Physics-based Communication Constraints}}, year = {2021} } - . Robust and efficient forward, differential, and inverse kinematics using dual quaternions. The International Journal of Robotics Research (IJRR). 10-11. 2021.
Modern approaches for robot kinematics employ the product of exponentials formulation, represented using homogeneous transformation matrices. Quaternions over dual numbers are an established alternative representation; however, their use presents certain challenges: the dual quaternion exponential and logarithm contain a zero-angle singularity, and many common operations are less efficient using dual quaternions than with matrices. We present a new derivation of the dual quaternion exponential and logarithm that removes the singularity, we show an implicit representation of dual quaternions offers analytical and empirical efficiency advantages compared with both matrices and explicit dual quaternions, and we derive efficient dual quaternion forms of differential and inverse position kinematics. Analytically, implicit dual quaternions are more compact and require fewer arithmetic instructions for common operations, including chaining and exponentials. Empirically, we demonstrate a 30--40% speedup on forward kinematics and a 300--500% speedup on inverse position kinematics. This work relates dual quaternions with modern exponential coordinates and demonstrates that dual quaternions are a robust and efficient representation for robot kinematics.
@article{dantam2020robust, author = {Neil T. Dantam}, number = {10-11}, volume = {40}, pages = {1087-1105}, journal = {The International Journal of Robotics Research (IJRR)}, title = {\href{http://dx.doi.org/10.1177/0278364920931948}{Robust and efficient forward, differential, and inverse kinematics using dual quaternions}}, year = {2021} } - . Learning Feasibility for Task and Motion Planning in Tabletop Environments. IEEE Robotics and Automation Letters (RA-L). 2. 2019.
Task and motion planning (TMP) combines discrete search and continuous motion planning. Earlier work has shown that to efficiently find a task-motion plan, the discrete search can leverage information about the continuous geometry. However, incorporating continuous elements into discrete planners presents challenges. We improve the scalability of TMP algorithms in tabletop scenarios with a fixed robot by introducing geometric knowledge into a constraint-based task planner in a robust way. The key idea is to learn a classifier for feasible motions and to use this classifier as a heuristic to order the search for a task-motion plan. The learned heuristic guides the search towards feasible motions and thus reduces the total number of motion planning attempts. A critical property of our approach is allowing robust planning in diverse scenes. We train the classifier on minimal exemplar scenes and then use principled approximations to apply the classifier to complex scenarios in a way that minimizes the effect of errors. By combining learning with planning, our heuristic yields order-of-magnitude run time improvements in diverse tabletop scenarios. Even when classification errors are present, properly biasing our heuristic ensures we will have little computational penalty.
@article{wells2019learning, author = {Wells, Andrew and Neil T. Dantam and Anshumali Shrivastava and Lydia E. Kavraki}, number = {2}, volume = {4}, pages = {1255--1262}, journal = {IEEE Robotics and Automation Letters (RA-L)}, title = {\href{http://dx.doi.org/10.1109/LRA.2019.2894861}{Learning Feasibility for Task and Motion Planning in Tabletop Environments}}, year = {2019} } - . Platform-Independent Benchmarks for Task and Motion Planning. IEEE Robotics and Automation Letters (RA-L). 4. 2018.
We present the first platform-independent evaluation method for Task and Motion Planning (TAMP). Previously point, various problems have been used to test individual planners for specific aspects of TAMP. However, no common set of metrics, formats, and problems have been accepted by the community. We propose a set of benchmark problems covering the challenging aspects of TAMP and a planner-independent specification format for these problems. Our objective is to better evaluate and compare TAMP planners, foster communication and progress within the field, and lay a foundation to better understand this class of planning problems.
@article{lagriffoul2018benchmark, author = {Fabien Lagriffoul and Neil T. Dantam and Garrett, Caelan and Akbari, Aliakbar and Siddharth Srivastava and Lydia E. Kavraki}, number = {4}, volume = {3}, pages = {3765--3772}, journal = {IEEE Robotics and Automation Letters (RA-L)}, title = {\href{http://dx.doi.org/10.1109/LRA.2018.2856701}{Platform-Independent Benchmarks for Task and Motion Planning}}, year = {2018} } - . An Incremental Constraint-Based Framework for Task and Motion Planning. The International Journal of Robotics Research (IJRR). 10. 2018.
We present a new algorithm for task and motion planning (TMP) and discuss the requirements and abstrations necessary to obtain robust solutions for TMP in general. Our Iteratively Deepened Task and Motion Planning (IDTMP) method is probabilistically-complete and offers improved per- formance and generality compared to a similar, state-of-the- art, probabilistically-complete planner. The key idea of IDTMP is to leverage incremental constraint solving to efficiently add and remove constraints on motion feasibility at the task level. We validate IDTMP on a physical manipulator and evaluate scalability on scenarios with many objects and long plans, showing order-of-magnitude gains compared to the benchmark planner and a four-times self-comparison speedup from our extensions. Finally, in addition to describing a new method for TMP and its implementation on a physical robot, we also put forward requirements and abstractions for the development of similar planners in the future.
@article{dantam2018tmp, author = {Neil T. Dantam and Zachary K. Kingston and Swarat Chaudhuri and Lydia E. Kavraki}, number = {10}, volume = {37}, pages = {1134--1151}, journal = {The International Journal of Robotics Research (IJRR)}, title = {\href{http://dx.doi.org/10.1177/0278364918761570}{An Incremental Constraint-Based Framework for Task and Motion Planning}}, year = {2018} } - . The Task Motion Kit. Robotics and Automation Magazine (RAM), IEEE. 3. 2018.
Robots require novel reasoning systems to achieve complex objectives in new environments. Everyday activities in the physical world couple discrete and continuous reasoning. For example, to set the table in Fig. 1, the robot must make discrete decisions about which objects to pick and the order in which to do so, and execute these decisions by computing continuous motions to reach objects or desired locations. Robotics has traditionally treated these issues in isolation. Reasoning about discrete events is referred to as task planning while reasoning about and computing continuous motions is the realm of motion planning. However, several recent works have shown that separating task planning from motion planning---that is finding first a series of actions that will later be executed through continuous motion---is problematic; for example, the next discrete action may specify picking an object, but there may be no continuous motion for the robot to bring its hand to a configuration that can actually grasp the object to pick it up. Instead, Task--Motion Planning (TMP) tightly couples task planning and motion planning, producing a sequence of steps that can actually be executed by a real robot to bring the world from an initial to a final state. This article provides an introduction to TMP and discusses the implementation and use of an open-source TMP framework that is adaptable to new robots, scenarios, and algorithms.
@article{dantam2018tmkit, author = {Neil T. Dantam and Swarat Chaudhuri and Lydia E. Kavraki}, number = {3}, volume = {25}, pages = {61--70}, publisher = {IEEE}, journal = {Robotics and Automation Magazine (RAM)}, title = {\href{http://dx.doi.org/10.1109/MRA.2018.2815081}{The Task Motion Kit}}, year = {2018} } - . Unix Philosophy and the Real World: Control Software for Humanoid Robots. Frontiers in Robotics and Artificial Intelligence, Research Topic on Software Architectures for Humanoid Robotics (FRAI). 2016.
Robot software combines the challenges of general purpose and real-time software, requiring complex logic and bounded resource use. Physical safety, particularly for dynamic systems such as humanoid robots, depends on correct software. General purpose computation has converged on unix-like operating systems -- standardized as POSIX, the Portable Operating System Interface -- for devices from cellular phones to supercomputers. The modular, multi-process design typical of POSIX applications is effective for building complex and reliable software. Absent from POSIX, however, is an interproccess communication mechanism that prioritizes newer data as typically desired for control of physical systems. We address this need in the Ach communication library which provides suitable semantics and performance for real-time robot control. Although initially designed for humanoid robots, Ach has broader applicability to complex mechatronic devices -- humanoid and otherwise -- that require real-time coupling of sensors, control, planning, and actuation. The initial user space implementation of Ach was limited in the ability to receive data from multiple sources. We remove this limitation by implementing Ach as a Linux kernel module, enabling Ach's high-performance and latest-message-favored semantics within conventional POSIX communication pipelines. We discuss how these POSIX interfaces and design principles apply to robot software, and we present a case study using the Ach kernel module for communication on the Baxter robot.
@article{dantam2016unix, author = {Neil T. Dantam and Bøndergaard, Kim and Johansson, Mattias A. and Furuholm, Tobias and Lydia E. Kavraki}, volume = {3}, journal = {Frontiers in Robotics and Artificial Intelligence, Research Topic on Software Architectures for Humanoid Robotics (FRAI)}, title = {\href{http://dx.doi.org/10.3389/frobt.2016.00006}{Unix Philosophy and the Real World: Control Software for Humanoid Robots}}, year = {2016} } - . The Ach IPC Library. Robotics and Automation Magazine (RAM), IEEE. 1. 2015.
Correct real-time software is vital for robots in safety-critical roles such as service and disaster response. These systems depend on software for locomotion, navigation, manipulation, and even seemingly innocuous tasks such as safely regulating battery voltage. A multi-process software design increases robustness by isolating errors to a single process, allowing the rest of the system to continue operating. This approach also assists with modularity and concurrency. For real-time tasks such as dynamic balance and force control of manipulators, it is critical to communicate the latest data sample with minimum latency. There are many communication approaches intended for both general purpose and real-time needs. Typical methods focus on reliable communication or network-transparency and accept a trade-off of increased message latency or the potential to discard newer data. By focusing instead on the specific case of real-time communication on a single host, we reduce communication latency and guarantee access to the latest sample. We present a new Interprocess Communication (IPC) library, Ach, which addresses this need, and discuss its application for real-time, multiprocess control on three humanoid robots.
@article{dantam2015multiprocess, author = {Neil T. Dantam and Daniel M. Lofaro and Ayonga Hereid and Paul Oh and Aaron Ames and Mike Stilman}, number = {1}, volume = {22}, pages = {76--85}, publisher = {IEEE}, journal = {Robotics and Automation Magazine (RAM)}, title = {\href{http://dx.doi.org/10.1109/MRA.2014.2356937}{The Ach IPC Library}}, year = {2015} } - . The Motion Grammar: Analysis of a Linguistic Method for Robot Control. Transactions on Robotics (T-RO), IEEE. 3. 2013.
We present the Motion Grammar: an approach to represent and verify robot control policies based on Context-Free Grammars. The production rules of the grammar represent a top-down task decomposition of robot behavior. The terminal symbols of this language represent sensor readings that are parsed in real-time. Efficient algorithms for context-free parsing guarantee that online parsing is computationally tractable. We analyze verification properties and language constraints of this linguistic modeling approach, show a linguistic basis that unifies several existing methods, and demonstrate effectiveness through experiments on a 14-DOF manipulator interacting with 32 objects (chess pieces) and an unpredictable human adversary. We provide many of the algorithms discussed as Open Source, permissively licensed software.
@article{dantam2013motion, author = {Neil T. Dantam and Mike Stilman}, number = {3}, volume = {29}, pages = {704--718}, publisher = {IEEE}, journal = {Transactions on Robotics (T-RO)}, title = {\href{http://dx.doi.org/10.1109/TRO.2013.2239553}{The Motion Grammar: Analysis of a Linguistic Method for Robot Control}}, year = {2013} }
Refereed Conference Papers
- 2023
- . Robot Team Data Collection with Anywhere Communication. International Conference on Intelligent Robots and Systems (IROS), IEEE/RSJ. 2023.
Using robots to collect data is an effective way to obtain information from the environment and communicate it to a static base station. Furthermore, robots have the capability to communicate with one another, potentially decreasing the time for data to reach the base station. We present a Mixed Integer Linear Program that reasons about discrete routing choices, continuous robot paths, and their effect on the latency of the data collection task. We analyze our formulation, discuss optimization challenges inherent to the data collection problem, and propose a factored formulation that finds optimal answers more efficiently. We show our work is able to find paths that reduce latency by up to 101% compared to treating all robots independently in our tested scenarios.
@inproceedings{schack2023communication, author = {Matthew A. Schack and John G. Rogers and Qi Han and Neil T. Dantam}, publisher = {IEEE/RSJ}, booktitle = {International Conference on Intelligent Robots and Systems (IROS)}, title = {Robot Team Data Collection with Anywhere Communication}, year = {2023} } - . Communication Jamming-Aware Robot Path Adaptation. International Conference on Distributed Computing in Smart Systems and the Internet of Things (DCOSS-IoT), IEEE. 2023.
Robot networks are necessary for a variety of monitoring and surveillance applications where robots must communicate observations. This work considers robot networks that must operate in an area affected by potential communication jamming and excessive radio frequency noise. Specifically, we look at deploying a reinforcement robot to strengthen an existing network of robots that are already performing a monitoring task. The robot's objective is to find a location that maximizes the network's signal-to-noise ratio. We present a Gaussian process approach to predict areas of excessive radio frequency noise, enabling the robot to avoid these areas and relay more data. We evaluate our algorithm's performance in physical robot experiments using a Clearpath Jackal robot and a USRP software-defined radio to broadcast a jamming signal. Our results show major improvements in networking metrics over a baseline and demonstrate the need for jamming-aware robot planning.
@inproceedings{diller2023communication, author = {Jonathan Diller and Neil T. Dantam and John G. Rogers and Qi Han}, publisher = {IEEE}, booktitle = {International Conference on Distributed Computing in Smart Systems and the Internet of Things (DCOSS-IoT)}, title = {\href{http://dx.doi.org/10.1109/DCOSS-IoT58021.2023.00120}{Communication Jamming-Aware Robot Path Adaptation}}, year = {2023} } - . Failure Explanation in Privacy-Sensitive Contexts: An Integrated Systems Approach. International Conference on Robot and Human Interactive Communication (ROMAN), IEEE. 2023.
In this paper, we explore how robots can properly explain failures during navigation tasks with privacy concerns. We present an integrated robotics approach to generate visual failure explanations, by combining a language-capable cognitive architecture (for recognizing intent behind commands), an object- and location-based context recognition system (for identifying the locations of people and classifying the context in which those people are situated) and an infeasibility proof-based motion planner (for explaining planning failures on the basis of contextually mediated privacy concerns). The behavior of this integrated system is validated using a series of experiments in a simulated medical environment.
@inproceedings{li2023failure, author = {Sihui Li and Sriram Siva and Terran Mott and Tom Williams and Hao Zhang and Neil T. Dantam}, publisher = {IEEE}, booktitle = {International Conference on Robot and Human Interactive Communication (ROMAN)}, title = {Failure Explanation in Privacy-Sensitive Contexts: An Integrated Systems Approach}, year = {2023} } - . Sample-Driven Connectivity Learning for Motion Planning in Narrow Passages. International Conference on Robotics and Automation (ICRA), IEEE. 2023.
Sampling-based motion planning works well in many cases but is less effective if the configuration space has narrow passages. In this paper, we propose a learning-based strategy to sample in these narrow passages, which improves overall planning time. Our algorithm first learns from the configuration space planning graphs and then uses the learned information to effectively generate narrow passage samples. We perform experiments in various 6-DOF and 7-DOF scenes, and our algorithm offers order of magnitude performance improvements compared to baseline planners in some of these scenarios.
@inproceedings{li2023SDCL, author = {Sihui Li and Neil T. Dantam}, pages = {5681-5687}, publisher = {IEEE}, booktitle = {International Conference on Robotics and Automation (ICRA)}, title = {\href{http://dx.doi.org/10.1109/ICRA48891.2023.10161339}{Sample-Driven Connectivity Learning for Motion Planning in Narrow Passages}}, year = {2023} } - . Exponential Convergence of Infeasibility Proofs for Kinematic Motion Planning. Algorithmic Foundations of Robotics XV (WAFR), Springer International Publishing. 2023.
Proving motion planning infeasibility is an important part of a complete motion planner. Common approaches for high-dimensional motion planning are only probabilistically complete. Previously, we presented an algorithm to construct infeasibility proofs by applying machine learning to sampled configurations from a bidirectional sampling-based planner. In this work, we prove that the learned manifold converges to an infeasibility proof exponentially. Combining prior approaches for sampling-based planning and our converging infeasibility proofs, we propose the term asymptotic completeness to describe the property of returning a plan or infeasibility proof in the limit. We compare the empirical convergence of different sampling strategies to validate our analysis.
@inproceedings{li2022exponential, author = {Sihui Li and Neil T. Dantam}, pages = {294--311}, publisher = {Springer International Publishing}, booktitle = {Algorithmic Foundations of Robotics XV (WAFR)}, title = {\href{http://dx.doi.org/10.1007/978-3-031-21090-7_18}{Exponential Convergence of Infeasibility Proofs for Kinematic Motion Planning}}, year = {2023} } - 2022
- . Givenness Hierarchy Informed Optimal Sentence Planning for Situated Human-Robot Interaction. International Conference on Intelligent Robots and Systems (IROS), IEEE/RSJ. 2022.
Robots that use natural language in collaborative tasks must refer to objects in their environment. Recent work has shown the utility of the linguistic theory of the Givenness Hierarchy (GH) in generating appropriate referring forms. But before referring expression generation (REG), collaborative robots must the determine content and structure of a sequence of utterances, a task known as document planning in the natural language generation (NLG) community. This problem presents additional challenges for robots in situated contexts, where described objects change both physically and in the minds of their interlocutors. In this work, we consider how robots can "think ahead" about the objects they must refer to and how to refer to them, sequencing object references to form a coherent, easy to follow chain. Specifically, we leverage GH to enable robots to plan their utterances in a way that keeps objects at a high cognitive status, which enables use of concise, anaphoric referring forms. We encode these linguistic insights as a mixed integer program (MIP) within a planning context, formulating constraints to concisely and efficiently capture GH-theoretic cognitive properties. We demonstrate that this GH-informed planner generates sequences of utterances with high inter-sentential coherence, which we argue should enable substantially more efficient and natural human-robot dialogue.
@inproceedings{spevak2022givenness, author = {Spevak, Kevin and Han, Zhao and Tom Williams and Neil T. Dantam}, pages = {6109-6115}, publisher = {IEEE/RSJ}, booktitle = {International Conference on Intelligent Robots and Systems (IROS)}, title = {\href{http://dx.doi.org/10.1109/IROS47612.2022.9981811}{Givenness Hierarchy Informed Optimal Sentence Planning for Situated Human-Robot Interaction}}, year = {2022} } - 2021
- . An Integrated Approach to Context-Sensitive Moral Cognition in Robot Cognitive Architectures. International Conference on Intelligent Robots and Systems (IROS), IEEE/RSJ. 2021. Best Paper Award on Cognitive Robotics Finalist
Acceptance of social robots in human-robot collaborative environments depends on the robots' sensitivity to human moral and social norms. Robot behavior that violates norms may decrease trust and lead human interactants to blame the robot and view it negatively. Hence, for long-term acceptance, social robots need to detect possible norm violations in their action plans and refuse to perform such plans. This paper integrates the Distributed, Integrated, Affect, Reflection, Cognition (DIARC) robot architecture (implemented in the Agent Development Environment (ADE)) with a novel place recognition module and a norm-aware task planner to achieve context-sensitive moral reasoning. This will allow the robot to reject inappropriate commands and comply with context-sensitive norms. In a validation scenario, our results show that the robot would not comply with a human command to violate a privacy norm in a private context.
@inproceedings{jackson2021integrated, author = {Jackson, Ryan Blake and Sihui Li and Banisetty, Santosh Balajee and Siva, Sriram and Zhang, Hao and Neil T. Dantam and Tom Williams}, pages = {1911--1918}, publisher = {IEEE/RSJ}, booktitle = {International Conference on Intelligent Robots and Systems (IROS)}, title = {\href{http://dx.doi.org/10.1109/IROS51168.2021.9636434}{An Integrated Approach to Context-Sensitive Moral Cognition in Robot Cognitive Architectures}}, year = {2021} } - . Optimization-Based Robot Team Exploration Considering Attrition and Communication Constraints. International Conference on Intelligent Robots and Systems (IROS), IEEE/RSJ. 2021.
Exploring robots may fail due to environmental hazards. Thus, robots need to account for the possibility of failure to plan the best exploration paths. Optimizing expected utility enables robots to find plans that balance achievable reward with the inherent risks of exploration. Moreover, when robots rendezvous and communicate to exchange observations, they increase the probability that at least one robot is able to return with the map. Optimal exploration is NP-hard, so we apply a constraint-based approach to enable highly-engineered solution techniques. We model exploration under the possibility of robot failure and communication constraints as an integer, linear program and a generalization of the Vehicle Routing Problem. Empirically, we show that for several scenarios, this formulation produces paths within 50% of a theoretical optimum and achieves twice as much reward as a baseline greedy approach.
@inproceedings{schack2021disconnection, author = {Matthew A. Schack and John G. Rogers and Qi Han and Neil T. Dantam}, pages = {5864--5871}, publisher = {IEEE/RSJ}, booktitle = {International Conference on Intelligent Robots and Systems (IROS)}, title = {\href{http://dx.doi.org/10.1109/IROS51168.2021.9636029}{Optimization-Based Robot Team Exploration Considering Attrition and Communication Constraints}}, year = {2021} } - . Learning Proofs of Motion Planning Infeasibility. Robotics: Science and Systems (RSS). 2021.
We present a learning-based approach to prove infeasibility of kinematic motion planning problems. Sampling-based motion planners are effective in high-dimensional spaces but are only probabilistically complete. Consequently; these planners cannot provide a definite answer if no plan exists; which is important for high-level scenarios; such as task-motion planning. We propose a combination of bidirectional sampling-based planning (such as RRT-connect) and machine learning to construct an infeasibility proof alongside the two search trees. An infeasibility proof is a closed manifold in the obstacle region of the configuration space that separates the start and goal into disconnected components of the free configuration space. We train the manifold using common machine learning techniques and then triangulate the manifold into a polytope to prove containment in the obstacle region. Under assumptions about learning hyper-parameters and robustness of configuration space optimization; the output is either an infeasibility proof or a motion plan. We demonstrate proof construction for 3-DOF and 4-DOF manipulators and show improvement over previous algorithms.
@inproceedings{li2021learning, author = {Sihui Li and Neil T. Dantam}, booktitle = {Robotics: Science and Systems (RSS)}, title = {\href{http://dx.doi.org/10.15607/RSS.2021.XVII.064}{Learning Proofs of Motion Planning Infeasibility}}, year = {2021} } - 2020
- . Towards General Infeasibility Proofs in Motion Planning. International Conference on Intelligent Robots and Systems (IROS), IEEE/RSJ. 2020.
We present a general approach for constructing proofs of motion planning infeasibility. Effective high-dimensional motion planners, such as sampling-based methods, are limited to probabilistic completeness, so when no plan exists, these planners either do not terminate or can only run until a timeout. We address this completeness challenge by augmenting a sampling-based planner with a method to create an infeasibility proof in conjunction with building the search tree. An infeasibility proof is a closed polytope that separates the start and goal into disconnected components of the free configuration space. We identify possible facets of the polytope via a nonlinear optimization procedure using sampled points in the non-free configuration space. We identify the set of facets forming the separating polytope via a linear constraint satisfaction problem. This proof construction is valid for general (i.e., non-Cartesian) configuration spaces. We demonstrate this approach on the low-dimensional Jaco manipulator and discuss engineering approaches to scale to higher dimensional spaces.
@inproceedings{li2020towards, author = {Sihui Li and Neil T. Dantam}, pages = {6704-6710}, publisher = {IEEE/RSJ}, booktitle = {International Conference on Intelligent Robots and Systems (IROS)}, title = {\href{http://dx.doi.org/10.1109/IROS45743.2020.9340804}{Towards General Infeasibility Proofs in Motion Planning}}, year = {2020} } - . Practical Exponential Coordinates using Implicit Dual Quaternions. Algorithmic Foundations of Robotics XIII (WAFR), Springer International Publishing. 2020.
Modern approaches for robot kinematics employ the product of exponentials formulation, represented using homogeneous transformation matrices. Quaternions over dual numbers are an established alternative representation; however, their use presents certain challenges: the dual quaternion exponential and logarithm contain a zero-angle singularity, and many common operations are less efficient using dual quaternions than with matrices. We present a new derivation of the dual quaternion exponential and logarithm that removes the singularity, and we show an implicit representation of dual quaternions offers analytical and empirical efficiency advantages compared to both matrices and explicit dual quaternions. Analytically, implicit dual quaternions are more compact and require fewer arithmetic instructions for common operations, including chaining and exponentials. Empirically, we demonstrate a 25%-40% speedup to compute the forward kinematics of multiple robots. This work offers a practical connection between dual quaternions and modern exponential coordinates, demonstrating that a quaternion-based approach provides a more efficient alternative to matrices for robot kinematics.
@inproceedings{dantam2018practical, author = {Neil T. Dantam}, pages = {639--655}, publisher = {Springer International Publishing}, booktitle = {Algorithmic Foundations of Robotics XIII (WAFR)}, title = {\href{http://dx.doi.org/10.1007/978-3-030-44051-0_37}{Practical Exponential Coordinates using Implicit Dual Quaternions}}, year = {2020} } - 2018
- . Augmented, Mixed, and Virtual Reality Enabling of Robot Deixis. Virtual, Augmented and Mixed Reality: Interaction, Navigation, Visualization, Embodiment, and Simulation (VAMR). 2018.
When humans interact with each other, they often make use of deictic gestures such as pointing to help pick out targets of interest to their conversation. In the field of Human-Robot Interaction, research has repeatedly demonstrated the utility of enabling robots to use such gestures as well. Recent work in augmented, mixed, and virtual reality stands to enable enormous advances in robot deixis, both by allowing robots to gesture in ways that were not previously feasible, and by enabling gesture on robotic platforms and environmental contexts in which gesture was not previously feasible. In this paper, we summarize our own recent work on using augmented, mixed, and virtual-reality techniques to advance the state-of-the-art of robot-generated deixis.
@inproceedings{williams2018augmented, author = {Tom Williams and Tran, Nhan and Rands, Josh and Neil T. Dantam}, editor = {Chen, Jessie Y.C. and Fragomeni, Gino}, pages = {257--275}, booktitle = {Virtual, Augmented and Mixed Reality: Interaction, Navigation, Visualization, Embodiment, and Simulation (VAMR)}, title = {\href{http://dx.doi.org/10.1007/978-3-319-91581-4_19}{Augmented, Mixed, and Virtual Reality Enabling of Robot Deixis}}, year = {2018} } - 2016
- . Incremental Task and Motion Planning: A Constraint-Based Approach. Robotics: Science and Systems (RSS). 2016.
We present a new algorithm for task and motion planning (TMP) and discuss the requirements and abstractions necessary to obtain robust solutions for TMP in general. Our Iteratively Deepened Task and Motion Planning (IDTMP) method is probabilistically-complete and offers improved per- formance and generality compared to a similar, state-of-the- art, probabilistically-complete planner. The key idea of IDTMP is to leverage incremental constraint solving to efficiently add and remove constraints on motion feasibility at the task level. We validate IDTMP on a physical manipulator and evaluate scalability on scenarios with many objects and long plans, showing order-of-magnitude gains compared to the benchmark planner and a four-times self-comparison speedup from our extensions. Finally, in addition to describing a new method for TMP and its implementation on a physical robot, we also put forward requirements and abstractions for the development of similar planners in the future.
@inproceedings{dantam2016tmp, author = {Neil T. Dantam and Zachary K. Kingston and Swarat Chaudhuri and Lydia E. Kavraki}, booktitle = {Robotics: Science and Systems (RSS)}, title = {\href{http://dx.doi.org/10.15607/RSS.2016.XII.002}{Incremental Task and Motion Planning: A Constraint-Based Approach}}, year = {2016} } - . Task and Motion Policy Synthesis as Liveness Games. International Conference on Automated Planning and Scheduling (ICAPS), AAAI. 2016.
We present a novel and scalable policy synthesis approach for robots. Rather than producing single-path plans for a static environment, we consider changing environments with uncontrollable agents, where the robot needs a policy to respond correctly over the infinite-horizon interaction with the environment. Our approach operates on task and motion domains, and combines actions over discrete states with continuous, collision-free paths. We synthesize a task and motion policy by iteratively generating a candidate policy and verifying its correctness. For efficient policy generation, we use grammars for potential policies to limit the search space and apply domain-specific heuristics to generalize verification failures, providing stricter constraints on policy candidates. For efficient policy verification, we construct compact, symbolic constraints for valid policies and employ a Satisfiability Modulo Theories (SMT) solver to check the validity of these constraints. Furthermore, the SMT solver enables quantitative specifications such as energy limits. The results show that our approach offers better scalability compared to a state-of-the-art policy synthesis tool in the tested benchmarks and demonstrate an order-of-magnitude speedup from our heuristics for the tested mobile manipulation domain.
@inproceedings{wang2016task, author = {Wang, Yue and Neil T. Dantam and Swarat Chaudhuri and Lydia E. Kavraki}, publisher = {AAAI}, booktitle = {International Conference on Automated Planning and Scheduling (ICAPS)}, title = {Task and Motion Policy Synthesis as Liveness Games}, year = {2016} } - 2015
- . Kinematically Constrained Workspace Control via Linear Optimization. International Conference on Humanoid Robots (Humanoids), IEEE. 2015.
We present a method for Cartesian workspace control of a robot manipulator that enforces joint-level acceleration, velocity, and position constraints using linear optimization. This method is robust to kinematic singularities. On redundant manipulators, we avoid poor configurations near joint limits by including a maximum permissible velocity term to center each joint within its limits. Compared to the baseline Jacobian damped least-squares method of workspace control, this new approach honors kinematic limits, ensuring physically realizable control inputs and providing smoother motion of the robot. We demonstrate our method on simulated redundant and non-redundant manipulators and implement it on the physical 7-degree-of-freedom Baxter manipulator. We provide our control software under a permissive license.
@inproceedings{kingston2015lc3, author = {Zachary K. Kingston and Neil T. Dantam and Lydia E. Kavraki}, pages = {758--764}, publisher = {IEEE}, booktitle = {International Conference on Humanoid Robots (Humanoids)}, title = {\href{http://dx.doi.org/10.1109/HUMANOIDS.2015.7363455}{Kinematically Constrained Workspace Control via Linear Optimization}}, year = {2015} } - 2014
- . Online Multi-Camera Registration for Bimanual Workspace Trajectories. International Conference on Humanoid Robots (Humanoids), IEEE. 2014. Best Paper Finalist, Mike Stilman Award Finalist
We demonstrate that millimeter-level bimanual manipulation accuracy can be achieved without the static camera registration typically required for visual servoing. We register multiple cameras online, converging in seconds, by visually tracking features on the robot hands and filtering the result. Then, we compute and track continuous-velocity relative workspace trajectories for the end-effector. We demonstrate the approach using Schunk LWA4 and SDH manipulators and Logitech C920 cameras, showing accurate relative positioning for pen-capping and object hand-off tasks. Our filtering software is available under a permissive license.
@inproceedings{dantam2014multi, author = {Neil T. Dantam and Heni Ben Amor and Henrik Christensen and Mike Stilman}, pages = {588--593}, publisher = {IEEE}, booktitle = {International Conference on Humanoid Robots (Humanoids)}, title = {\href{http://dx.doi.org/10.1109/HUMANOIDS.2014.7041422}{Online Multi-Camera Registration for Bimanual Workspace Trajectories}}, year = {2014} } - . Spherical Parabolic Blends for Robot Workspace Trajectories. International Conference on Intelligent Robots and Systems (IROS), IEEE. 2014.
We present a new approach to generate workspace trajectories for multiple waypoints. To satisfy workspace constraints with constant-axis rotation, this method splines a given sequence of orientations, maintaining constant-axis within each segment. This improves on other approaches which are point-to-point or take indirect paths. We derive this approach by blending subsequent spherical linear interpolation phases, computing interpolation parameters so that rotational velocity is continuous. We show this method first on simulated manipulator and then perform a physical screwing task on a Schunk LWA4 robot arm. Finally, we provide permissively licensed software which implements this trajectory generation and tracking.
@inproceedings{dantam2014spherical, author = {Neil T. Dantam and Mike Stilman}, pages = {3624--3629}, publisher = {IEEE}, booktitle = {International Conference on Intelligent Robots and Systems (IROS)}, title = {\href{http://dx.doi.org/10.1109/IROS.2014.6943070}{Spherical Parabolic Blends for Robot Workspace Trajectories}}, year = {2014} } - . Online Camera Registration for Robot Manipulation. International Symposium on Experimental Robotics (ISER), Springer. 2014.
We demonstrate that millimeter-level manipulation accuracy can be achieved without the static camera registration typically required for visual servoing. We register the camera online, converging in seconds, by visually tracking features on the robot and filtering the result. This online registration handles cases such as perturbed camera positions, wear and tear on camera mounts, and even a camera held by a human. We implement the approach on a Schunk LWA4 manipulator and Logitech C920 camera, servoing to target and pre-grasp configurations. Our filtering software is available under a permissive license.
@inproceedings{dantam2014online, author = {Neil T. Dantam and Heni Ben Amor and Henrik Christensen and Mike Stilman}, pages = {179--194}, publisher = {Springer}, booktitle = {International Symposium on Experimental Robotics (ISER)}, title = {\href{http://dx.doi.org/10.1007/978-3-319-23778-7_13}{Online Camera Registration for Robot Manipulation}}, year = {2014} } - 2013
- . Correct Software Synthesis for Stable Speed-Controlled Robotic Walking. Robotics: Science and Systems (RSS). 2013.
We present a software synthesis method for speed-controlled robot walking based on supervisory control of a context-free Motion Grammar. First, we use Human-Inspired control to identify parameters for stable fixed speed walking and for transitions between fixed speeds. Next, we build a Motion Grammar representing the discrete-time control for this set of speeds. Then, we synthesize C code from this grammar and generate supervisors online to achieve desired walking speeds, ensuring correctness of discrete behavior. Finally, we demonstrate this approach on the Aldebaran NAO, showing stable walking transitions with dynamically selected speeds.
@inproceedings{dantam2013correct, author = {Neil T. Dantam and Ayonga Hereid and Aaron Ames and Mike Stilman}, booktitle = {Robotics: Science and Systems (RSS)}, title = {\href{http://roboticsproceedings.org/rss09/p40.html}{Correct Software Synthesis for Stable Speed-Controlled Robotic Walking}}, year = {2013} } - . Multi-Process Control Software for Humanoid Robots. IEEE International Conference on Technologies for Practical Robot Applications (TEPRA). 2013.
Humanoid robots require greater software reliability than traditional mechantronic systems if they are to perform useful tasks in typical human-oriented environments. This paper covers a software architecture which distributes the load of computation and control tasks over multiple processes, enabling fail-safes within the software. These fail-safes ensure that unexpected crashes or latency do not produce damaging behavior in the robot. The distribution also offers benefits for future software development by making the architecture modular and extensible. Utilizing a low-latency inter-process communication protocol (Ach), processes are able to communicate with high control frequencies. The key motivation of this software architecture is to provide a practical framework for safe and reliable humanoid robot software development. The authors test and verify this framework on a HUBO2 Plus humanoid robot.
@inproceedings{grey2013architecture, author = {M.X. Grey and Neil T. Dantam and Daniel M. Lofaro and Paul Oh and Aaron Bobick and Magnus Egerstedt and Mike Stilman}, pages = {190--195}, booktitle = {IEEE International Conference on Technologies for Practical Robot Applications (TEPRA)}, title = {\href{http://dx.doi.org/10.1109/TePRA.2013.6556374}{Multi-Process Control Software for Humanoid Robots}}, year = {2013} } - 2012
- . Robust and Efficient Communication for Real-Time Multi-Process Robot Software. International Conference on Humanoid Robots (Humanoids), IEEE. 2012.
We present a new Interprocess Communication (IPC) mechanism and library. Ach is uniquely suited for coordinating drivers, controllers, and algorithms in complex robotic systems such as humanoid robots. Ach eliminates the Head-of-Line Blocking problem for applications that always require access to the newest message. Ach is efficient, robust, and formally verified. It has been tested and demonstrated on a variety of physical robotic systems, and we discuss the implementation on our humanoid robot Golem Krang. Finally, the source code for Ach is available under an Open Source permissive license.
@inproceedings{dantam2012ach, author = {Neil T. Dantam and Mike Stilman}, pages = {316--322}, publisher = {IEEE}, booktitle = {International Conference on Humanoid Robots (Humanoids)}, title = {\href{http://dx.doi.org/10.1109/HUMANOIDS.2012.6651538}{Robust and Efficient Communication for Real-Time Multi-Process Robot Software}}, year = {2012} } - . Linguistic Transfer of Human Assembly Tasks to Robots. Intelligent Robots and Systems (IROS), IEEE. 2012.
We demonstrate the automatic transfer of an assembly task from human to robot. This work extends efforts showing the utility of linguistic models in verifiable robot control policies by now performing real visual analysis of human demonstrations to automatically extract a policy for the task. This method tokenizes each human demonstration into a sequence of object connection symbols, then transforms the set of sequences from all demonstrations into an automaton, which represents the task-language for assembling a desired object. Finally, we combine this assembly automaton with a kinematic model of a robot arm to reproduce the demonstrated task.
@inproceedings{dantam2012assem, author = {Neil T. Dantam and Irfan Essa and Mike Stilman}, publisher = {IEEE}, booktitle = {Intelligent Robots and Systems (IROS)}, title = {\href{http://dx.doi.org/10.1109/IROS.2012.6385749}{Linguistic Transfer of Human Assembly Tasks to Robots}}, year = {2012} } - . Linguistic Composition of Semantic Maps and Hybrid Controllers. International Symposium on Experimental Robotics (ISER). 2012.
This work combines semantic maps with hybrid control models, generating a direct link between action and environment models to produce a control policy for mobile manipulation in unstructured environments. First, we generate a semantic map for our environment and design a base model of robot action. Then, we combine this map and action model using the Motion Grammar Calculus to produce a combined robot-environment model. Using this combined model, we apply supervisory control to produce a policy for the manipulation task. We demonstrate this approach on a Segway RMP-200 mobile platform.
@inproceedings{dantam2012composition, author = {Neil T. Dantam and Carlos Nieto-Granda and Henrik Christensen and Mike Stilman}, pages = {699--714}, booktitle = {International Symposium on Experimental Robotics (ISER)}, title = {\href{http://dx.doi.org/10.1007/978-3-319-00065-7_47}{Linguistic Composition of Semantic Maps and Hybrid Controllers}}, year = {2012} } - . The Motion Grammar Calculus for Context-Free Hybrid Systems. American Control Conference (ACC). 2012. Best Presentation in Session
This paper provides a method for deriving provably correct controllers for Hybrid Dynamical Systems with Context-Free discrete dynamics, nonlinear continuous dynamics, and nonlinear state partitioning. The proposed method models the system using a Context-Free Motion Grammar and specifies correct performance using a Regular language representation such as Linear Temporal Logic. The initial model is progressively rewritten via a calculus of symbolic transformation rules until it satisfies the desired specification.
@inproceedings{dantam2012calc, author = {Neil T. Dantam and Mike Stilman}, pages = {5294--5301}, booktitle = {American Control Conference (ACC)}, title = {\href{http://dx.doi.org/10.1109/ACC.2012.6315290}{The Motion Grammar Calculus for Context-Free Hybrid Systems}}, year = {2012} } - 2011
- . The Motion Grammar: Linguistic Perception, Planning, and Control. Robotics: Science and Systems (RSS). 2011.
We present and analyze the Motion Grammar: a novel unified representation for task decomposition, perception, planning, and control that provides both fast online control of robots in uncertain environments and the ability to guarantee completeness and correctness. The grammar represents a policy for the task which is parsed in real-time based on perceptual input. Branches of the syntax tree form the levels of a hierarchical decomposition, and the individual robot sensor readings are given by tokens. We implement this approach in the interactive game of Yamakuzushi on a physical robot resulting in a system that repeatably competes with a human opponent in sustained game-play for the roughly six minute duration of each match.
@inproceedings{dantam2011yama, author = {Neil T. Dantam and Mike Stilman}, booktitle = {Robotics: Science and Systems (RSS)}, title = {\href{http://www.roboticsproceedings.org/rss07/p07.html}{The Motion Grammar: Linguistic Perception, Planning, and Control}}, year = {2011} } - . The Motion Grammar for Physical Human-Robot Games. International Conference on Robotics and Automation (ICRA), IEEE. 2011. SAIC/Georgia Tech Achievement Award
We introduce the Motion Grammar, a powerful new representation for robot decision making, and validate its properties through the successful implementation of a /physical/ human-robot game. The Motion Grammar is a formal tool for task decomposition and hybrid control in the presence of significant online uncertainty. In this paper, we describe the Motion Grammar, introduce some of the formal guarantees it can provide, and represent the entire game of human-robot chess through a single formal language. This language includes game-play, safe handling of human motion, uncertainty in piece positions, misplaced and collapsed pieces. We demonstrate the simple and effective language formulation through experiments on a 14-DOF manipulator interacting with 32 objects (chess pieces) and an unpredictable human adversary.
@inproceedings{dantam2011chess, author = {Neil T. Dantam and Pushkar Kolhe and Mike Stilman}, publisher = {IEEE}, booktitle = {International Conference on Robotics and Automation (ICRA)}, title = {\href{http://dx.doi.org/10.1109/ICRA.2011.5980468}{The Motion Grammar for Physical Human-Robot Games}}, year = {2011} } - 2010
- . Dynamic Pushing Strategies for Dynamically Stable Mobile Manipulators. International Conference on Robotics and Automation (ICRA), IEEE. 2010.
This paper presents three effective manipulation strategies for wheeled, dynamically balancing robots with articulated links. By comparing these strategies through analysis simulation and robot experiments, we show that contact placement and body posture have a significant impact on the robot's ability to accelerate and displace environment objects. Given object geometry and friction parameters we determine the most effective methods for utilizing wheel torque to perform non-prehensile manipulation.
@inproceedings{kolhe2010pushing, author = {Pushkar Kolhe and Neil T. Dantam and Mike Stilman}, publisher = {IEEE}, booktitle = {International Conference on Robotics and Automation (ICRA)}, title = {\href{http://dx.doi.org/10.1109/ROBOT.2010.5509491}{Dynamic Pushing Strategies for Dynamically Stable Mobile Manipulators}}, year = {2010} }
Workshop Papers
- . Learning Explicit Infeasibility from Implicit Configuration Space Connectivity. RSS Workshop on Implicit Representations for Robotic Manipulation. 2022.
Sampling-based algorithms generate plans using samples from implicit representations of high dimensional configuration spaces. These samples contain unexploited information, which can be use to build a better understanding towards the configuration space's connectivity. We aim to use these samples as data to learn explicit infeasibility proofs. Previous work has shown success in up-to 4 DoF manipulation scenes. In this work, we focus on improving the learning step of the previous algorithm and show experimental results on a 5-DoF manipulator.
@inproceedings{li2022implicit, author = {Sihui Li and Neil T. Dantam}, booktitle = {RSS Workshop on Implicit Representations for Robotic Manipulation}, title = {Learning Explicit Infeasibility from Implicit Configuration Space Connectivity}, year = {2022} } - . Representations for Scheduling of Heterogeneous Computation to Support Motion Planning. RSS Workshop on Implicit Representations for Robotic Manipulation. 2022.
Heterogeneous (multi-accelerator) chips are becoming commonplace in many robotics applications due to their ability to accelerate multiple types of computational workloads. By effectively using these devices, robotic tasks can be performed faster or with less resource usage. However, robotic systems present a variety of requirements for scheduling on such devices, especially on mobile robots. These include both time-critical requirements based on physical constraints (e.g., computing fast enough to safely handle unexpected obstacles) and resource constraints (e.g., battery life). By considering these limitations while scheduling, it is possible to expand the safe operation area of a robot. Additionally, changing environments can modify these constraints. In planning situations, this can then impact the optimal plan, as the physical environment may impact viable schedules. Thus, situations can arise where a longer path uses less resources by allowing more efficient schedules. Currently, there is no general, formalized way to reason about these constraints and the tradeoffs they present. A more formal system of reasoning about these tradeoffs also allows them to be considered in higher level tasks, such as Task and Motion Planning. To solve this problem, we propose the creation of a structured system, the Constrained Autonomous Workload Scheduler (CAuWS). By using a representative language (AuWL), Timed Petri nets, and mixed-integer linear programming, CAuWS offers novel capabilities to represent heterogeneous computation alongside physical constraints, optimization criteria, and motion planning. This enables robots to optimally leverage new computational platforms. We demonstrate CAuWS with a simulation of a drone running vision tasks under multiple physical constraints, showing CAuWS is practical for dynamic environments and obeys physical constraints.
@inproceedings{mcgowen2022representations, author = {McGowen, Justin and Dagli, Ismet and Mehmet Belviranli and Neil T. Dantam}, booktitle = {RSS Workshop on Implicit Representations for Robotic Manipulation}, title = {Representations for Scheduling of Heterogeneous Computation to Support Motion Planning}, year = {2022} } - . Bayesian-Markov Feedback in Constraint-based Planning. ICRA Workshop on Human-Robot Teaming Beyond Human Operational Speeds. 2019.
Planning under uncertainty presents numerous challenges in expressivity and scalability. We propose a new algorithm that extends the constraint-based planning framework to address state uncertainty. The approach has produced optimal plans in simulation, and we are implementing it on a physical robot.
@inproceedings{schack2019bayesianplanning, author = {Matthew A. Schack and Neil T. Dantam}, booktitle = {ICRA Workshop on Human-Robot Teaming Beyond Human Operational Speeds}, title = {\href{https://manihsieh.com/icra-2019-workshop-program/}{Bayesian-Markov Feedback in Constraint-based Planning}}, year = {2019} } - . Fault Recovery in Logical Manipulation Policies. Workshop on Human versus Robot Grasping and Manipulation, RSS. 2014.
In real-world systems, failures happen. Reliably executing manipulation tasks depends on handling errors and faults. Typical approaches for logical task planning identify a single execution path, without considering faults. This eases computation, but presents a challenge when the robot must respond to unexpected conditions. The principal challenge in explicitly representing policies for logical domains is handling the state space that is potentially in the number of propositions. We can address this challenge by using a linguistic, hierarchical representation for manipulation task policies. Using a language-based policy representation, we can compactly encode desired execution, potential faults, and the appropriate response. We consider two types of errors and how they may be handled. First, we consider subtask or action failure, such as a missed grasp, where a chosen action does not produce the desired effect. Second, we consider uncontrollable events, such a force limits, where some transition occurs unpredictable or unavoidably. In both of these cases, we can use a language-based approach to continue and recover.
@inproceedings{dantam2014fault, author = {Neil T. Dantam and Heni Ben Amor and Henrik Christensen and Mike Stilman}, booktitle = {Workshop on Human versus Robot Grasping and Manipulation, RSS}, title = {\href{http://mobilemanipulation.org/rss2014/index.php/acceptedposters}{Fault Recovery in Logical Manipulation Policies}}, year = {2014} } - . Software-Synthesis via LL(*) for Context-Free Robot Programs. 4th Workshop on Formal Methods for Robotics and Automation, RSS. 2013.
Producing reliable software for robotic systems requires formal techniques to ensure correctness. Some popular approaches model the discrete dynamics and computation of the robot using finite state automata or linear temporal logic. We can represent more complicated systems and tasks, and still retain key guarantees on verifiability and runtime performance, by modeling the system instead with a context-free grammar. The challenge with a context-free model is the need for a more advanced software synthesis algorithm. We address this challenge by adapting the LL(*) parser generation algorithm, originally developed for program translation, to the domain of online robot control. We demonstrate this LL(*) parser generation implementation in the Motion Grammar Kit, permitting synthesis for robot control software for complex, hierarchical, and recursive tasks.
@inproceedings{rouhani2013software, author = {Rouhani, Arash and Neil T. Dantam and Mike Stilman}, booktitle = {4th Workshop on Formal Methods for Robotics and Automation, RSS}, title = {Software-Synthesis via LL(*) for Context-Free Robot Programs}, year = {2013} } - . Make Your Robot Talk Correctly: Deriving Models of Hybrid System. RSS Workshop on Grounding Human-Robot Dialog for Spatial Tasks. 2011.
Using both formal language and differential equations to model a robotic system, we introduce a calculus of transformation rules for the symbolic derivation of hybrid controllers. With a Context-Free Motion Grammar, we show how to test reachability between different regions of state-space and give several symbolic transformations to modify the set of event strings the system may generate. This approach lets one modify the language of the hybrid system, providing a way to change system behavior so that it satisfies linguistic constraints on correct operation.
@inproceedings{dantam2010talk, author = {Neil T. Dantam and Magnus Egerstedt and Mike Stilman}, booktitle = {RSS Workshop on Grounding Human-Robot Dialog for Spatial Tasks}, title = {\href{http://projects.csail.mit.edu/spatial/workshop}{Make Your Robot Talk Correctly: Deriving Models of Hybrid System}}, year = {2011} }
Technical Reports
- . The Task Motion Kit. Department of Computer Science, Rice University. TR16-12. 2016.
Expanding the capabilities of robots to achieve complex objectives in new environments requires novel reasoning systems. Everyday tasks in the physical world, such as table setting, couple discrete decisions about objects and actions with geometric decisions about collision free motion. Robotics has traditionally treated these issues---task planning and motion planning---in isolation, thus missing their potential interactions. Instead, the joint approach of Task--Motion Planning (TMP) addresses this inherent coupling. Moreover, reasoning in concert about overall objectives and concrete motions enables the high-level specification of behavior, mitigating typically intensive system integration efforts required in robotics. We address the need for underlying models and principles in integrated robot manipulation with a new planning and execution framework that is adaptable to new robots, domains, and algorithms.
@techreport{dantam2016tr1602, author = {Neil T. Dantam and Swarat Chaudhuri and Lydia E. Kavraki}, number = {TR16-12}, institution = {Department of Computer Science, Rice University}, title = {\href{https://hdl.handle.net/1911/96418}{The Task Motion Kit}}, year = {2016} } - . Algorithms for Linguistic Robot Policy Inference from Demonstration of Assembly Tasks. Georgia Insitute of Technology. GT-GOLEM-2012-002. 2012.
We describe several algorithms used for the inference of linguistic robot policies from human demonstration. First, tracking and match objects using the Hungarian Algorithm. Then, we convert Regular Expressions to Nondeterministic Finite Automata (NFA) using the McNaughton-Yamada-Thompson Algorithm. Next, we use Subset Construction to convert to a Deterministic Finite Automaton. Finally, we minimize finite automata using either Hopcroft's Algorithm or Brzozowski's Algorithm.
@techreport{dantam2012algorithms, author = {Neil T. Dantam and Irfan Essa and Mike Stilman}, number = {GT-GOLEM-2012-002}, institution = {Georgia Insitute of Technology}, title = {\href{https://hdl.handle.net/1853/43194}{Algorithms for Linguistic Robot Policy Inference from Demonstration of Assembly Tasks}}, year = {2012} } - . Ach: IPC for Real-Time Robot Control. Georgia Insitute of Technology. GT-GOLEM-2011-003. 2011.
We present a new Inter-Process Communication (IPC) mechanism and library. Ach is uniquely suited for coordinating perception, control drivers, and algorithms in real-time systems that sample data from physical processes. Ach eliminates the Head-of-Line Blocking problem for applications that always require access to the newest message. Ach is efficient, robust, and formally verified. It has been tested and demonstrated on a variety of physical robotic systems. Finally the source code for Ach is available under an Open Source BSD-style license.
@techreport{dantam2011achtech, author = {Neil T. Dantam and Mike Stilman}, number = {GT-GOLEM-2011-003}, institution = {Georgia Insitute of Technology}, title = {\href{https://hdl.handle.net/1853/40934}{Ach: IPC for Real-Time Robot Control}}, year = {2011} } - . Equations of Motion for Dynamically Stable Mobile Manipulators. College of Computing. Georgia Institute of Technology. GT-GOLEM-2010-002. 2010.
This paper derives the equations of motion for Sparky, a mobile manipulator robot. These equations are used in the manipulation analysis, simulation, and experiments of "Dynamic Pushing Strategies for Dynamically Stable Mobile Manipulators."
@techreport{dantam2010equations, author = {Neil T. Dantam and Pushkar Kolhe and Mike Stilman}, number = {GT-GOLEM-2010-002}, institution = {College of Computing. Georgia Institute of Technology}, title = {\href{https://hdl.handle.net/1853/36489}{Equations of Motion for Dynamically Stable Mobile Manipulators}}, year = {2010} } - . The Motion Grammar: Linguistic Perception, Planning, and Control. College of Computing. Georgia Institute of Technology. GT-GOLEM-2010-001. 2010.
We present the Motion Grammar: a novel unified representation for task decomposition, perception, planning, and hybrid control that provides a computationally tractable way to control robots in uncertain environments with guarantees on completeness and correctness. The grammar represents a policy for the task which is parsed in real-time based on perceptual input. Branches of the syntax tree form the levels of a hierarchical decomposition, and the individual robot sensor readings are given by tokens. We implement this approach in the interactive game of Yamakuzushi on a physical robot resulting in a system that repeatably competes with a human opponent in sustained game-play for matches up to six minutes.
@techreport{dantam2010yamatech, author = {Neil T. Dantam and Mike Stilman}, number = {GT-GOLEM-2010-001}, institution = {College of Computing. Georgia Institute of Technology}, title = {\href{https://hdl.handle.net/1853/36485}{The Motion Grammar: Linguistic Perception, Planning, and Control}}, year = {2010} }