About

Zak Kingston is a Ph.D. candidate in Computer Science at Rice University, working with Dr. Lydia Kavraki. He graduated with a B.S. in Computer Science from Rice in Spring 2016 and a M.S. in Computer Science from Rice in December 2017. He is currently funded by a NASA NSTRF fellowship, working with the Robonaut 2 team. His research interests lie in algorithmic robotics, focusing on robot manipulation planning and planning with constraints.

More details can be found in his curriculum vitae .

Code

Constrained Planning in OMPL

The generic constrained planning framework presented in ISRR 2017 and IJRR 2019 is now available in OMPL! Take a look at the overview and the tutorial.


Experience

Kavraki Lab @ Rice University

ZK is currently Ph.D. student in the Kavraki Robotics Lab at Rice University, working on robot manipulation planning.

Dexterous Robotics Lab @ NASA JSC
ZK is an NSTRF Fellow with NASA Johnson Space Center's Dexterous Robotics Lab. He previously developed the motion planning system for NASA’s humanoid robot Robonaut 2.
MRSL @ Rice University
ZK used to work in the Multi-Robot Systems Lab (MRSL) at Rice University, where he worked on multi-robot manipulation.

Publications

Peer-Reviewed Journal Articles

2019

J3.

Exploring Implicit Spaces for Constrained Sampling-Based Planning
Zachary Kingston, Mark Moll, and Lydia E. Kavraki

Abstract / Bibtex / PDF / Publisher

We present a review and reformulation of manifold constrained sampling-based motion planning within a unifying framework, IMACS (implicit manifold configuration space). IMACS enables a broad class of motion planners to plan in the presence of manifold constraints, decoupling the choice of motion planning algorithm and method for constraint adherence into orthogonal choices. We show that implicit configuration spaces defined by constraints can be presented to sampling-based planners by addressing two key fundamental primitives, sampling and local planning, and that IMACS preserves theoretical properties of probabilistic completeness and asymptotic optimality through these primitives. Within IMACS, we implement projection- and continuation-based methods for constraint adherence, and demonstrate the framework on a range of planners with both methods in simulated and realistic scenarios. Our results show that the choice of method for constraint adherence depends on many factors and that novel combinations of planners and methods of constraint adherence can be more effective than previous approaches. Our implementation of IMACS is open source within the Open Motion Planning Library and is easily extended for novel planners and constraint spaces.


Close


@article{Kingston2019,
 abstract = {We present a review and reformulation of manifold constrained sampling-based motion planning within a unifying framework, IMACS (implicit manifold configuration space). IMACS enables a broad class of motion planners to plan in the presence of manifold constraints, decoupling the choice of motion planning algorithm and method for constraint adherence into orthogonal choices. We show that implicit configuration spaces defined by constraints can be presented to sampling-based planners by addressing two key fundamental primitives, sampling and local planning, and that IMACS preserves theoretical properties of probabilistic completeness and asymptotic optimality through these primitives. Within IMACS, we implement projection- and continuation-based methods for constraint adherence, and demonstrate the framework on a range of planners with both methods in simulated and realistic scenarios. Our results show that the choice of method for constraint adherence depends on many factors and that novel combinations of planners and methods of constraint adherence can be more effective than previous approaches. Our implementation of IMACS is open source within the Open Motion Planning Library and is easily extended for novel planners and constraint spaces.},
 author = {Zachary Kingston and Mark Moll and Lydia E. Kavraki},
 doi = {10.1177/0278364919868530},
 journal = {The International Journal of Robotics Research},
 month = {9},
 number = {10--11},
 pages = {1151--1178},
 title = {Exploring Implicit Spaces for Constrained Sampling-Based Planning},
 volume = {38},
 year = {2019}
}

Close


2018

J2.

An Incremental Constraint-Based Framework for Task and Motion Planning
Neil T. Dantam, Zachary Kingston, Swarat Chaudhuri, and Lydia E. Kavraki

Abstract / Bibtex / PDF / Publisher

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 performance 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.


Close


@article{Dantam2018,
 abstract = {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 performance 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.},
 author = {Neil T. Dantam and Zachary Kingston and Swarat Chaudhuri and Lydia E. Kavraki},
 doi = {10.1177/0278364918761570},
 journal = {The International Journal of Robotics Research, Special Issue on the 2016 Robotics: Science and Systems Conference},
 number = {10},
 pages = {1134--1151},
 title = {An Incremental Constraint-Based Framework for Task and Motion Planning},
 volume = {37},
 year = {2018}
}

Close


J1.

Sampling-Based Methods for Motion Planning with Constraints
Zachary Kingston, Mark Moll, and Lydia E. Kavraki

Abstract / Bibtex / PDF / Publisher

Robots with many degrees of freedom (e.g., humanoid robots and mobile manipulators) have increasingly been employed to accomplish realistic tasks in domains such as disaster relief, spacecraft logistics, and home caretaking. Finding feasible motions for these robots autonomously is essential for their operation. Sampling-based motion planning algorithms have been shown to be effective for these high-dimensional systems. However, incorporating task constraints (e.g., keeping a cup level, writing on a board) into the planning process introduces significant challenges. is survey describes the families of methods for sampling-based planning with constraints and places them on a spectrum delineated by their complexity. Constrained sampling-based methods are based upon two core primitive operations: (1) sampling constraint-satisfying configurations and (2) generating constraint-satisfying continuous motion. Although the basics of sampling-based planning are presented for contextual background, the survey focuses on the representation of constraints and sampling-based planners that incorporate constraints.


Close


@article{Kingston2018,
 abstract = {Robots with many degrees of freedom (e.g., humanoid robots and mobile manipulators) have increasingly been employed to accomplish realistic tasks in domains such as disaster relief, spacecraft logistics, and home caretaking. Finding feasible motions for these robots autonomously is essential for their operation. Sampling-based motion planning algorithms have been shown to be effective for these high-dimensional systems. However, incorporating task constraints (e.g., keeping a cup level, writing on a board) into the planning process introduces significant challenges. is survey describes the families of methods for sampling-based planning with constraints and places them on a spectrum delineated by their complexity. Constrained sampling-based methods are based upon two core primitive operations: (1) sampling constraint-satisfying configurations and (2) generating constraint-satisfying continuous motion. Although the basics of sampling-based planning are presented for contextual background, the survey focuses on the representation of constraints and sampling-based planners that incorporate constraints.},
 author = {Zachary Kingston and Mark Moll and Lydia E. Kavraki},
 doi = {10.1146/annurev-control-060117-105226},
 journal = {Annual Review of Control, Robotics, and Autonomous Systems},
 number = {1},
 pages = {159--185},
 title = {Sampling-Based Methods for Motion Planning with Constraints},
 volume = {1},
 year = {2018}
}

Close


Book Chapters

2020

B1.

Planning under Manifold Constraints, Encyclopedia of Robotics
Zachary Kingston
(Accepted)

Bibtex

@inbook{Kingston2020c,
 author = {Zachary Kingston},
 chapter = {Planning under Manifold Constraints},
 editor = {Marcelo H. Ang Jr. and Oussama Khatib and Bruno Siciliano},
 note = {Accepted},
 publisher = {Springer},
 title = {Encyclopedia of Robotics},
 year = {2020}
}

Close


Peer-Reviewed Conference Papers

2020

C8.

Informing Multi-Modal Planning with Synergistic Discrete Leads
Zachary Kingston, Andrew M. Wells, Mark Moll, and Lydia E. Kavraki

Abstract / Bibtex / PDF / Video

Robotic manipulation problems are inherently continuous, but typically have underlying discrete structure, e.g., whether or not an object is grasped. This means many problems are multi-modal and in particular have a continuous infinity of modes. For example, in a pick-and-place manipulation domain, every grasp and placement of an object is a mode. Usually manipulation problems require the robot to transition into different modes, e.g., going from a mode with an object placed to another mode with the object grasped. To successfully find a manipulation plan, a planner must find a sequence of valid single-mode motions as well as valid transitions between these modes. Many manipulation planners have been proposed to solve tasks with multi-modal structure. However, these methods require mode-specific planners and fail to scale to very cluttered environments or to tasks that require long sequences of transitions. This paper presents a general layered planning approach to multi-modal planning that uses a discrete "lead" to bias search towards useful mode transitions. The difficulty of achieving specific mode transitions is captured online and used to bias search towards more promising sequences of modes. We demonstrate our planner on complex scenes and show that significant performance improvements are tied to both our discrete "lead" and our continuous representation.


Close


@inproceedings{Kingston2020a,
 abstract = {Robotic manipulation problems are inherently continuous, but typically have underlying discrete structure, e.g., whether or not an object is grasped. This means many problems are multi-modal and in particular have a continuous infinity of modes. For example, in a pick-and-place manipulation domain, every grasp and placement of an object is a mode. Usually manipulation problems require the robot to transition into different modes, e.g., going from a mode with an object placed to another mode with the object grasped. To successfully find a manipulation plan, a planner must find a sequence of valid single-mode motions as well as valid transitions between these modes. Many manipulation planners have been proposed to solve tasks with multi-modal structure. However, these methods require mode-specific planners and fail to scale to very cluttered environments or to tasks that require long sequences of transitions. This paper presents a general layered planning approach to multi-modal planning that uses a discrete "lead" to bias search towards useful mode transitions. The difficulty of achieving specific mode transitions is captured online and used to bias search towards more promising sequences of modes. We demonstrate our planner on complex scenes and show that significant performance improvements are tied to both our discrete "lead" and our continuous representation.},
 author = {Zachary Kingston and Andrew M. Wells and Mark Moll and Lydia E. Kavraki},
 booktitle = {IEEE International Conference on Robotics and Automation},
 pages = {3199--3205},
 title = {Informing Multi-Modal Planning with Synergistic Discrete Leads},
 year = {2020}
}

Close


C7.

Decoupling Constraints from Sampling-Based Planners
Zachary Kingston, Mark Moll, and Lydia E. Kavraki

Abstract / Bibtex / PDF / Publisher / Video

We present a general unifying framework for sampling-based motion planning under kinematic task constraints which enables a broad class of planners to compute plans that satisfy a given constraint function that encodes, e.g., loop closure, balance, and end-effector constraints. The framework decouples a planner’s method for exploration from constraint satisfaction by representing the implicit configuration space defined by a constraint function. We emulate three constraint satisfaction methodologies from the literature, and demonstrate the framework with a range of planners utilizing these constraint methodologies. Our results show that the appropriate choice of constrained satisfaction methodology depends on many factors, e.g., the dimension of the configuration space and implicit constraint manifold, and number of obstacles. Furthermore, we show that novel combinations of planners and constraint satisfaction methodologies can be more effective than previous approaches. The framework is also easily extended for novel planners and constraint spaces.


Close


@incollection{Kingston2020b,
 abstract = {We present a general unifying framework for sampling-based motion planning under kinematic task constraints which enables a broad class of planners to compute plans that satisfy a given constraint function that encodes, e.g., loop closure, balance, and end-effector constraints. The framework decouples a planner’s method for exploration from constraint satisfaction by representing the implicit configuration space defined by a constraint function. We emulate three constraint satisfaction methodologies from the literature, and demonstrate the framework with a range of planners utilizing these constraint methodologies. Our results show that the appropriate choice of constrained satisfaction methodology depends on many factors, e.g., the dimension of the configuration space and implicit constraint manifold, and number of obstacles. Furthermore, we show that novel combinations of planners and constraint satisfaction methodologies can be more effective than previous approaches. The framework is also easily extended for novel planners and constraint spaces.},
 address = {Cham},
 author = {Zachary Kingston and Mark Moll and Lydia E. Kavraki},
 booktitle = {Robotics Research},
 doi = {10.1007/978-3-030-28619-4_62},
 editor = {Amato, N. M. and Hager, G. and Thomas, S. and Torres-Torriti, M.},
 isbn = {978-3-030-28619-4},
 pages = {913--928},
 publisher = {Springer International Publishing},
 title = {Decoupling Constraints from Sampling-Based Planners},
 year = {2020}
}

Close


2018

C6.

Distributed Object Characterization with Local Sensing by a Multi-Robot System
Golnaz Habibi, Sándor P. Fekete, Zachary Kingston, and James McLurkin

Abstract / Bibtex / PDF / Publisher / Video

This paper presents two distributed algorithms for enabling a swarm of robots with local sensing and local coordinates to estimate the dimensions and orientation of an unknown complex polygonal object, ie, its minimum and maximum width and its main axis. Our first approach is based on a robust heuristic of distributed Principal Component Analysis (DPCA), while the second is based on turning the idea of Rotating Calipers into a distributed algorithm (DRC). We simulate DRC and DPCA methods and test DPCA on real robots. The result show our algorithms successfully estimate the dimension and orientation of convex or concave objects with a reasonable error in the presence of noisy data.


Close


@incollection{Habibi2018,
 abstract = {This paper presents two distributed algorithms for enabling a swarm of robots with local sensing and local coordinates to estimate the dimensions and orientation of an unknown complex polygonal object, ie, its minimum and maximum width and its main axis. Our first approach is based on a robust heuristic of distributed Principal Component Analysis (DPCA), while the second is based on turning the idea of Rotating Calipers into a distributed algorithm (DRC). We simulate DRC and DPCA methods and test DPCA on real robots. The result show our algorithms successfully estimate the dimension and orientation of convex or concave objects with a reasonable error in the presence of noisy data.},
 author = {Golnaz Habibi and S{\'a}ndor P. Fekete and Zachary Kingston and James McLurkin},
 booktitle = {Distributed Autonomous Robotic Systems},
 doi = {10.1007/978-3-319-73008-0_15},
 editor = {Roderich Gro{\ss} and Andreas Kolling and Spring Berman and Emilio Frazzoli and Alcherio Martinoli and Fumitoshi Matsuno and Melvin Gauci},
 pages = {205--218},
 publisher = {Springer Proceedings in Advanced Robotics},
 title = {Distributed Object Characterization with Local Sensing by a Multi-Robot System},
 volume = {6},
 year = {2018}
}

Close


2017

C5.

Robonaut 2 and You: Specifying and Executing Complex Operations
William Baker, Zachary Kingston, Mark Moll, Julia Badger, and Lydia E. Kavraki

Abstract / Bibtex / PDF / Publisher / Video

Crew time is a precious resource due to the expense of trained human operators in space. Efficient caretaker robots could lessen the manual labor load required by frequent vehicular and life support maintenance tasks, freeing astronaut time for scientific mission objectives. Humanoid robots can fluidly exist alongside human counterparts due to their form, but they are complex and high-dimensional platforms. This paper describes a system that human operators can use to maneuver Robonaut 2 (R2), a dexterous humanoid robot developed by NASA to research co-robotic applications. The system includes a specification of constraints used to describe operations, and the supporting planning framework that solves constrained problems on R2 at interactive speeds. The paper is developed in reference to an illustrative, typical example of an operation R2 performs to highlight the challenges inherent to the problems R2 must face. Finally, the interface and planner is validated through a case-study using the guiding example on the physical robot in a simulated microgravity environment. This work reveals the complexity of employing humanoid caretaker robots and suggest solutions that are broadly applicable.


Close


@inproceedings{Baker2017,
 abstract = {Crew time is a precious resource due to the expense of trained human operators in space. Efficient caretaker robots could lessen the manual labor load required by frequent vehicular and life support maintenance tasks, freeing astronaut time for scientific mission objectives. Humanoid robots can fluidly exist alongside human counterparts due to their form, but they are complex and high-dimensional platforms. This paper describes a system that human operators can use to maneuver Robonaut 2 (R2), a dexterous humanoid robot developed by NASA to research co-robotic applications. The system includes a specification of constraints used to describe operations, and the supporting planning framework that solves constrained problems on R2 at interactive speeds. The paper is developed in reference to an illustrative, typical example of an operation R2 performs to highlight the challenges inherent to the problems R2 must face. Finally, the interface and planner is validated through a case-study using the guiding example on the physical robot in a simulated microgravity environment. This work reveals the complexity of employing humanoid caretaker robots and suggest solutions that are broadly applicable.},
 address = {Austin, TX},
 author = {William Baker and Zachary Kingston and Mark Moll and Julia Badger and Lydia E. Kavraki},
 booktitle = {IEEE Workshop on Advanced Robotics and its Social Impacts},
 doi = {10.1109/ARSO.2017.8025204},
 month = {March},
 pages = {1--8},
 title = {Robonaut 2 and You: Specifying and Executing Complex Operations},
 year = {2017}
}

Close


2016

C4.

Incremental Task and Motion Planning: A Constraint-Based Approach
Neil T. Dantam, Zachary Kingston, Swarat Chaudhuri, and Lydia E. Kavraki

Abstract / Bibtex / PDF / Publisher / Video

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 performance 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.


Close


@inproceedings{Dantam2016,
 abstract = {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 performance 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.},
 address = {Ann Arbor, MI},
 author = {Neil T. Dantam and Zachary Kingston and Swarat Chaudhuri and Lydia E. Kavraki},
 booktitle = {Robotics: Science and Systems},
 doi = {10.15607/RSS.2016.XII.002},
 month = {June},
 title = {Incremental Task and Motion Planning: A Constraint-Based Approach},
 year = {2016}
}

Close


2015

C3.

Kinematically Constrained Workspace Control via Linear Optimization
Zachary Kingston, Neil T. Dantam, and Lydia E. Kavraki

Abstract / Bibtex / PDF / Publisher / Video

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.


Close


@inproceedings{Kingston2015,
 abstract = {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.},
 author = {Zachary Kingston and Neil T. Dantam and Lydia E. Kavraki},
 booktitle = {IEEE-RAS International Conference on Humanoid Robots},
 doi = {10.1109/HUMANOIDS.2015.7363455},
 month = {Nov},
 pages = {758--764},
 title = {Kinematically Constrained Workspace Control via Linear Optimization},
 year = {2015}
}

Close


C2.

Pipelined Consensus for Global State Estimation in Multi-Agent Systems
Golnaz Habibi, Zachary Kingston, Zijian Wang, Mac Schwager, and James McLurkin

Abstract / Bibtex / PDF / Publisher / Publisher

This paper presents pipelined consensus, an extension of pair-wise gossip-based consensus, for multi-agent systems using mesh networks. Each agent starts a new consensus in each round of gossiping, and stores the intermediate results for the previous k consensus in a pipeline message. After k rounds of gossiping, the results of the first consensus are ready. The pipeline keeps each consensus independent, so any errors only persist for k rounds. This makes pipelined consensus robust to many real-world problems that other algorithms cannot handle, including message loss, changes in network topology, sensor variance, and changes in agent population. The algorithm is fully distributed and self-stabilizing, and uses a communication message of fixed size. We demonstrate the efficiency of pipelined consensus in two scenarios: computing mean sensor values in a distributed sensor network, and computing a centroid estimate in a multi-robot system. We provide extensive simulation results, and real-world experiments with up to 24 agents. The algorithm produces accurate results, and handles all of the disturbances mentioned above.


Close


@incollection{Habibi2015a,
 abstract = {This paper presents pipelined consensus, an extension of pair-wise gossip-based consensus, for multi-agent systems using mesh networks. Each agent starts a new consensus in each round of gossiping, and stores the intermediate results for the previous k consensus in a pipeline message. After k rounds of gossiping, the results of the first consensus are ready. The pipeline keeps each consensus independent, so any errors only persist for k rounds. This makes pipelined consensus robust to many real-world problems that other algorithms cannot handle, including message loss, changes in network topology, sensor variance, and changes in agent population. The algorithm is fully distributed and self-stabilizing, and uses a communication message of fixed size. We demonstrate the efficiency of pipelined consensus in two scenarios: computing mean sensor values in a distributed sensor network, and computing a centroid estimate in a multi-robot system. We provide extensive simulation results, and real-world experiments with up to 24 agents. The algorithm produces accurate results, and handles all of the disturbances mentioned above.},
 author = {Golnaz Habibi and Zachary Kingston and Zijian Wang and Mac Schwager and James McLurkin},
 booktitle = {Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems},
 doi = {10.5555/2772879.2773320},
 isbn = {9781450334136},
 pages = {1315--1323},
 publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
 title = {Pipelined Consensus for Global State Estimation in Multi-Agent Systems},
 url = {http://dl.acm.org/citation.cfm?id=2772879.2773320},
 year = {2015}
}

Close


C1.

Distributed Centroid Estimation and Motion Controllers for Collective Transport by Multi-Robot Systems
Golnaz Habibi, Zachary Kingston, William Xie, Mathew Jellins, and James McLurkin

Abstract / Bibtex / PDF / Publisher / Video

This paper presents four distributed motion controllers to enable a group of robots to collectively transport an object towards a guide robot. These controllers include: rotation around a pivot robot, rotation in-place around an estimated centroid of the object, translation, and a combined motion of rotation and translation in which each manipulating robot follows a trochoid path. Three of these controllers require an estimate of the centroid of the object, to use as the axis of rotation. Assuming the object is surrounded by manipulator robots, we approximate the centroid of the object by measuring the centroid of the manipulating robots. Our algorithms and controllers are fully distributed and robust to changes in network topology, robot population, and sensor error. We tested all of the algorithms in real-world environments with 9 robots, and show that the error of the centroid estimation is low, and that all four controllers produce reliable motion of the object.


Close


@inproceedings{Habibi2015b,
 abstract = {This paper presents four distributed motion controllers to enable a group of robots to collectively transport an object towards a guide robot. These controllers include: rotation around a pivot robot, rotation in-place around an estimated centroid of the object, translation, and a combined motion of rotation and translation in which each manipulating robot follows a trochoid path. Three of these controllers require an estimate of the centroid of the object, to use as the axis of rotation. Assuming the object is surrounded by manipulator robots, we approximate the centroid of the object by measuring the centroid of the manipulating robots. Our algorithms and controllers are fully distributed and robust to changes in network topology, robot population, and sensor error. We tested all of the algorithms in real-world environments with 9 robots, and show that the error of the centroid estimation is low, and that all four controllers produce reliable motion of the object.},
 author = {Golnaz Habibi and Zachary Kingston and William Xie and Mathew Jellins and James McLurkin},
 booktitle = {IEEE International Conference on Robotics and Automation},
 doi = {10.1109/ICRA.2015.7139356},
 pages = {1282--1288},
 title = {Distributed Centroid Estimation and Motion Controllers for Collective Transport by Multi-Robot Systems},
 year = {2015}
}

Close


Theses

2017

T1.

A Unifying Framework for Constrained Sampling-Based Planning
Zachary Kingston

Abstract / Bibtex / PDF

Complex robots with many degrees-of-freedom (e.g., humanoids, mobile manipulators) have been increasingly applied to achieve tasks in fields such as disaster relief or spacecraft logistics. Finding motions for these systems autonomously is necessary if they are to be applied in unstructured environments not known a priori, as they must compute motions on-the-fly. Sampling-based motion planning algorithms have been shown to be effective for finding motions for high-dimensional systems such as these. However, the problems these robots face typically take the form of tasks with constraints, which limit the valid motions a robot can take (e.g., turning a valve about its axis, carrying a tray with both arms, etc.). Incorporating constraints while planning introduces significant challenges, as constraints induce a lower-dimensional manifold of constraint-satisfying configurations within the robot's configuration space. The lower-dimensional structure of the manifold throws a wrench into the basic operation of a sampling-based planner, necessitating a constraint methodology to provide a means for the planner to satisfy constraints. Within the literature, many constrained sampling-based motion planning methods have been proposed for sampling-based planning with constraints. Each of these methods introduces a constraint methodology of their own to tackle the issues raised when considering constraints. This thesis organizes several previously proposed constraint methodologies along of a spectrum, cataloged by the amount of bookkeeping and computation used to approximate the manifold of constraint-satisfying configurations. Notably, previous constrained sampling-based methods augment a single sampling-based algorithm with their constraint methodology to create a bespoke planner. This thesis presents a general framework for sampling-based motion planning with geometric constraints, unifying prior works by approaching the constrained motion planning problem at a higher level of abstraction. The framework decouples the constraint methodology from the planner's method for exploration by presenting the constraint-induced manifold as a configuration space to the planner, hiding details of the constraint methodology behind the space's primitive operations. Three constraint methodologies from the literature are emulated within the framework. The framework is demonstrated with a range of planners using the three emulated constraint methodologies in a set of simulated problems. Results show the advantages decoupling brings to constrained sampling-based planning, with novel combinations of planners and constraint methodologies surpassing emulated prior works. The framework is also easily extended for novel planners and constraint spaces.


Close


@mastersthesis{Kingston2017MS,
 abstract = {Complex robots with many degrees-of-freedom (e.g., humanoids, mobile manipulators) have been increasingly applied to achieve tasks in fields such as disaster relief or spacecraft logistics. Finding motions for these systems autonomously is necessary if they are to be applied in unstructured environments not known a priori, as they must compute motions on-the-fly. Sampling-based motion planning algorithms have been shown to be effective for finding motions for high-dimensional systems such as these. However, the problems these robots face typically take the form of tasks with constraints, which limit the valid motions a robot can take (e.g., turning a valve about its axis, carrying a tray with both arms, etc.). Incorporating constraints while planning introduces significant challenges, as constraints induce a lower-dimensional manifold of constraint-satisfying configurations within the robot's configuration space. The lower-dimensional structure of the manifold throws a wrench into the basic operation of a sampling-based planner, necessitating a constraint methodology to provide a means for the planner to satisfy constraints. Within the literature, many constrained sampling-based motion planning methods have been proposed for sampling-based planning with constraints. Each of these methods introduces a constraint methodology of their own to tackle the issues raised when considering constraints. This thesis organizes several previously proposed constraint methodologies along of a spectrum, cataloged by the amount of bookkeeping and computation used to approximate the manifold of constraint-satisfying configurations. Notably, previous constrained sampling-based methods augment a single sampling-based algorithm with their constraint methodology to create a bespoke planner. This thesis presents a general framework for sampling-based motion planning with geometric constraints, unifying prior works by approaching the constrained motion planning problem at a higher level of abstraction. The framework decouples the constraint methodology from the planner's method for exploration by presenting the constraint-induced manifold as a configuration space to the planner, hiding details of the constraint methodology behind the space's primitive operations. Three constraint methodologies from the literature are emulated within the framework. The framework is demonstrated with a range of planners using the three emulated constraint methodologies in a set of simulated problems. Results show the advantages decoupling brings to constrained sampling-based planning, with novel combinations of planners and constraint methodologies surpassing emulated prior works. The framework is also easily extended for novel planners and constraint spaces.},
 address = {Houston, TX},
 author = {Zachary Kingston},
 school = {Rice University},
 title = {A Unifying Framework for Constrained Sampling-Based Planning},
 year = {2017}
}

Close


A picture of me from February 2020.

Contact

zakrice.edu
Duncan Hall 3052