@article{ghosh-wafr-2018
, author = "Mukulika Ghosh and Shawna Thomas and Nancy M. Amato"
, title = "Fast Collision Detection for Motion Planning Using Shape Primitive Skeletons"
, journal = "Algorithmic Foundations of Robotics XIII. Springer Proceedings in Advanced Robotics (SPAR)"
, publisher = "Springer, Cham."
, volume = "14"
, pages = "36-51"
, year = "2020"
, doi = "10.1007/978-3-030-44051-0_3"
}

In many robotics applications, the environment (robots and obstacles) often have very complex geometries. These result in expensive primitive computations such as collision detection which in turn, affect the overall performance of these applications. Approximating the geometry is a common approach to optimize computation. Unlike other applications of geometric approximation where it is applied to one space (usually obstacle space), we approximate both obstacle and free workspace with a set of geometric shape primitives that are completely contained within the space and represent its topology (skeleton). We use these “shape primitive skeletons” to improve collision detection performance in motion planning algorithms. Our results show that the use of shape primitive skeletons improves the performance of standard collision detection methods in motion planning problems by 20–70% in our 2D and 3D test environments regardless of motion planning strategy. We also show how the same shape primitive skeletons can be used with robots of different sizes to improve the performance of collision detection operation.

@phdthesis{ghosh-phd-2019
, author = "Mukulika Ghosh"
, title = "Geometric Approximations and Their Application to Motion Planning"
, school = "Department of Computer Science and Engineering, Texas A\&M University"
, month = "August"
, year = "2019"
, note = "https://oaktrust.library.tamu.edu/handle/1969.1/187961"
}

Geometric approximation methods are a preferred solution to handle complexities (such as a large volume or complex features such as concavities) in geometric objects or environments containing them. Complexities often pose a computational bottleneck for applications such as motion planning. Exact resolution of these complexities might introduce other complexities such as unmanageable number of components. Hence, approximation methods provide a way to handle these complexities in a manageable state by trading off some accuracy. In this dissertation, two novel geometric approximation methods are studied: aggregation hierarchy and shape primitive skeleton. The aggregation hierarchy is a hierarchical clustering of polygonal or polyhedral objects. The shape primitive skeleton provides an approximation of bounded space as a skeleton of shape primitives. These methods are further applied to improve the performance of motion planning applications. We evaluate the methods in environments with 2D and 3D objects. The aggregation hierarchy groups nearby objects into individual objects. The hierarchy is created by varying the distance threshold that determines which objects are nearby. This creates levels of detail of the environment. The hierarchy of the obstacle space is then used to create a decom-position of the complementary space (i.e, free space) into a set of sampling regions to improve the efficiency and accuracy of the sampling operation of the sampling based motion planners. Our results show that the method can improve the efficiency (10 − 70% of planning time) of sampling based motion planning algorithms. The shape primitive skeleton inscribes a set of shape primitives (e.g., sphere, boxes) inside a bounded space such that they represent the skeleton or the connectivity of the space. We apply the shape primitive skeletons of the free space and obstacle space in motion planning problems to improve the collision detection operation. Our results also show the use of shape primitive skeleton in both spaces improves the performance of collision detectors (by 20 − 70% of collision detection time) used in motion planning algorithms. In summary, this dissertation evaluates how geometric approximation methods can be applied to improve the performance of motion planning methods, especially, sampling based motion planning methods

@inproceedings{ghosh2016motion,
title={Motion planning using hierarchical aggregation of workspace obstacles},
author={Ghosh, Mukulika and Thomas, Shawna and Morales, Marco and Rodriguez, Sam and Amato, Nancy M},
booktitle={2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
pages={5716--5721},
year={2016},
organization={IEEE}
}

Sampling-based motion planning is the state-of-the-art technique for solving challenging motion planning problems in a wide variety of domains. While generally successful, their performance suffers from increasing problem complexity. In many cases, the full problem complexity is not needed for the entire solution. We present a hierarchical aggregation framework that groups and models sets of obstacles based on the currently needed level of detail. The hierarchy enables sampling to be performed using the simplest and most conservative representation of the environment possible in that region. Our results show that this scheme improves planner performance irrespective of the underlying sampling method and input problem. In many cases, improvement is significant, with running times often less than 60% of the original planning time.

TODO: Ghosh, Mukulika (2012). Fast Approximate Convex Decomposition. Master's thesis, Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /ETD -TAMU -2012 -08 -11873.

Approximate convex decomposition (ACD) is a technique that partitions an input object into "approximately convex" components. Decomposition into approximately convex pieces is both more efficient to compute than exact convex decomposition and can also generate a more manageable number of components. It can be used as a basis of divide-and-conquer algorithms for applications such as collision detection, skeleton extraction and mesh generation. In this paper, we propose a new method called Fast Approximate Convex Decomposition (FACD) that improves the quality of the decomposition and reduces the cost of computing it for both 2D and 3D models. In particular, we propose a new strategy for evaluating potential cuts that aims to reduce the relative concavity, rather than absolute concavity. As shown in our results, this leads to more natural and smaller decompositions that include components for small but important features such as toes or fingers while not decomposing larger components, such as the torso that may have concavities due to surface texture. Second, instead of decomposing a component into two pieces at each step, as in the original ACD, we propose a new strategy that uses a dynamic programming approach to select a set of n_c non-crossing (independent) cuts that can be simultaneously applied to decompose the component into n_c + 1 components. This reduces the depth of recursion and, together with a more efficient method for computing the concavity measure, leads to significant gains in efficiency. We provide comparative results for 2D and 3D models illustrating the improvements obtained by FACD over ACD and we compare with the segmentation methods given in the Princeton Shape Benchmark.

@inproceedings{10.1145/1236246.1236265,
author = {Lien, Jyh-Ming and Amato, Nancy M.},
title = {Approximate Convex Decomposition of Polyhedra},
year = {2007},
isbn = {9781595936660},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1236246.1236265},
doi = {10.1145/1236246.1236265},
abstract = {Decomposition is a technique commonly used to partition complex models into simpler components. While decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this paper we explore an alternative partitioning strategy that decomposes a given model into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficiently. Indeed, for many applications, an approximate convex decomposition (ACD) can more accurately represent the important structural features of the model by providing a mechanism for ignoring less significant features, such as surface texture. We describe a technique for computing ACDs of three-dimensional polyhedral solids and surfaces of arbitrary genus. We provide results illustrating that our approach results in high quality decompositions with very few components and applications showing that comparable or better results can be obtained using ACD decompositions in place of exact convex decompositions (ECD) that are several orders of magnitude larger.},
booktitle = {Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling},
pages = {121–131},
numpages = {11},
keywords = {concavity measurement, convex decomposition},
location = {Beijing, China},
series = {SPM '07}
}

Decomposition is a technique commonly used to partition complex models into simpler components. While decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this paper we explore an alternative partitioning strategy that decomposes a given model into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficiently. Indeed, for many applications, an approximate convex decomposition (ACD) can more accurately represent the important structural features of the model by providing a mechanism for ignoring less significant features, such as surface texture. We describe a technique for computing ACDs of three-dimensional polyhedral solids and surfaces of arbitrary genus. We provide results illustrating that our approach results in high quality decompositions with very few components and applications showing that comparable or better results can be obtained using ACD decompositions in place of exact convex decompositions (ECD) that are several orders of magnitude larger.

@phdthesis{lien2006approximate,
title={Approximate convex decomposition and its applications},
author={Lien, Jyh-Ming},
volume={69},
number={01},
year={2006}
}

Geometric computations are essential in many real-world problems. One important issue in geometric computations is that the geometric models in these problems can be so large that computations on them have infeasible storage or computation time requirements. Decomposition is a technique commonly used to partition complex models into simpler components. Whereas decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this work, we have developed an approximate technique, called Approximate Convex Decomposition (ACD), which decomposes a given polygon or polyhedron into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficently. Indeed, for many applications, an ACD can represent the important structural features of the model more accurately by providing a mechanism for ignoring less significant features, such as wrinkles and surface texture. Our study of a wide range of applications shows that in addition to providing computational efficiency, ACD also provides natural multi-resolution or hierarchical representations. In this dissertation, we provide some examples of ACD's many potential applications, such as particle simulation, mesh generation, motion planning, and skeleton extraction.

@inproceedings{10.1145/1128888.1128919,
author = {Lien, Jyh-Ming and Keyser, John and Amato, Nancy M.},
title = {Simultaneous Shape Decomposition and Skeletonization},
year = {2006},
isbn = {1595933581},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1128888.1128919},
doi = {10.1145/1128888.1128919},
booktitle = {Proceedings of the 2006 ACM Symposium on Solid and Physical Modeling},
pages = {219–228},
numpages = {10},
keywords = {skeletonization, convex decomposition, multi-resolution skeleton},
location = {Cardiff, Wales, United Kingdom},
series = {SPM '06}
}

Shape decomposition and skeletonization share many common properties and applications. However, they are generally treated as independent computations. In this paper, we propose an iterative approach that simultaneously generates a hierarchical shape decomposition and a corresponding set of multi-resolution skeletons. In our method, a skeleton of a model is extracted from the components of its decomposition --- that is, both processes and the qualities of their results are interdependent. In particular, if the quality of the extracted skeleton does not meet some user specified criteria, then the model is decomposed into finer components and a new skeleton is extracted from these components. The process of simultaneous shape decomposition and skeletonization iterates until the quality of the skeleton becomes satisfactory. We provide evidence that the proposed framework is efficient and robust under perturbation and. deformation. We also demonstrate that our results can readily be used in problems including skeletal deformations and virtual reality navigation.

@inproceedings{ la-acd-04
, author = "J.-M. Lien and N. M. Amato"
, title = "Approximate Convex Decomposition"
, booktitle = "Proc.\ 20th Annual {ACM} Symp.\ Computat.\ Geom.\ (SoCG)"
, year = "2004"
, month = "June"
, note = "Video Abstract."
, pages = "457--458"
}

Not applicable (it is a video abstract)

@inproceedings{ la-acdp-04
, author = "J.-M. Lien and N. M. Amato"
, title = "Approximate Convex Decomposition of Polygons"
, booktitle = "Proc.\ 20th Annual {ACM} Symp.\ Computat.\ Geom.\ (SoCG)"
, year = "2004"
, month="June"
, pages = "17--26"
}

We propose a strategy to decompose a polygon, containing zero or more holes, into ``approximately convex'' pieces. For many applications, the approximately convex components of this decomposition provide similar benefits as convex components, while the resulting decomposition is significantly smaller and can be computed more efficiently. Moreover, our approximate convex decomposition (ACD) provides a mechanism to focus on key structural features and ignore less significant artifacts such as wrinkles and surface texture a user specified tolerance determines allowable concavity. We propose a simple algorithm that computes an ACD of a polygon by iteratively removing (resolving) the most significant non-convex feature (notch). As a by product, it produces an elegant hierarchical representation that provides a series of `increasingly convex' decompositions. Our algorithm computes an ACD of a simple polygon with n vertices and r notches in O(nr) time. In contrast, exact convex decomposition is NP-hard or,if the polygon has no holes, takes O(nr2) time.