Lehigh University logo
Lehigh University logo
Mechanical Engineering and Mechanics
Subhrajit Bhattacharya

Project Highlights


Topological Path Planning and it Applications

We use topological invariants (homotopy and homology invariants) to augment graph search-based path planning algorithms in order to find optimal paths in different homotopy/homology classes. This lets us solve optimal motion planning for systems involving cables as well as problems such as multi-robot topological exploration.

[ + ]   Representative Publications
  1. Subhrajit Bhattacharya, "Topological and Geometric Techniques in Graph-Search Based Robot Planning", PhD thesis, University of Pennsylvania, 2012. (BibTeX)
    [   PDF of thesis  |  Presentation and movies  |  Addendum  ]
  2. Subhrajit Bhattacharya, David Lipsky, Robert Ghrist and Vijay Kumar, "Invariants for Homology Classes with Application to Optimal Search and Planning Problem in Robotics", Annals of Mathematics and Artificial Intelligence (AMAI), 67(3):251-281, Springer, March, 2013. DOI: 10.1007/s10472-013-9357-7. (BibTeX)
  3. Subhrajit Bhattacharya, Maxim Likhachev and Vijay Kumar, "Topological Constraints in Search-based Robot Path Planning", Autonomous Robots, 33(3):273-290, Springer Netherlands, October, 2012. DOI: 10.1007/s10514-012-9304-1. (BibTeX)
    [   PDF on Springer web-site  |  Supplementary videos on Springer web-site  ||   Application to topological object separation  |  Related paper on Homotopy path planning  |  AMAI'13 paper with generalization to arbitrary dimension  ||   Old Code for the 2D results appearing in the AAAI paper  ::   MATLAB code for uniformly discretized environment  |  MATLAB code for visibility graph  |  C++ code (planning with homotopy class constraints & homotopy class exploration with dynamic obstacles & non-Euclidean cost)  ||   Newer implementations using the YAGSBPL library  ::   Bare-bones C++ implementation of homology/homotopy path planning in 2D (YAGSBPL 2.1 included)  |  Implementation of differential (N-1)-form for D-dimensional Euclidean spaces with obstacles (based on AMAI paper) and topological path planning in 3-dimensional space (YAGSBPL 2.0 included)  ]
  4. Subhrajit Bhattacharya, Maxim Likhachev and Vijay Kumar, "Identification and Representation of Homotopy Classes of Trajectories for Search-based Path Planning in 3D", [Original title: Identifying Homotopy Classes of Trajectories for Robot Exploration and Path Planning] [Winner of Best Paper Award]. In Proceedings of Robotics: Science and Systems. 27-30 June, 2011. (BibTeX)
  5. Subhrajit Bhattacharya and Robert Ghrist, "Path Homotopy Invariants and their Application to Optimal Trajectory Planning", In Proceedings of IMA Conference on Mathematics of Robotics (IMAMR). St Anne's College, University of Oxford, September 9-11, 2015. (BibTeX)
    [  PDF  |  conference website  ]
  6. Subhrajit Bhattacharya and Robert Ghrist, "Path Homotopy Invariants and their Application to Optimal Trajectory Planning", electronic pre-print, 2017. arXiv:1710.02871 [cs.RO]. (BibTeX)
  7. Subhrajit Bhattacharya, Robert Ghrist and Vijay Kumar, "Persistent Homology for Path Planning in Uncertain Environments", IEEE Transactions on Robotics (T-RO), 31(3):578-590, March, 2015. DOI: 10.1109/TRO.2015.2412051. (BibTeX)
  8. Subhrajit Bhattacharya, Soonkyum Kim, Hordur Heidarsson, Gaurav Sukhatme and Vijay Kumar, "A Topological Approach to using cables to separate and manipulate sets of objects", International Journal of Robotics Research, 34(6):799-815, April, 2015. DOI: 10.1177/0278364914562236. (BibTeX)
  9. Dhanushka Kularatne, Subhrajit Bhattacharya and M. Ani Hsieh, "Time and Energy Optimal Path Planning in General Flows", In Proceedings of the Robotics: Science and System (RSS). June, 2016. (BibTeX)
  10. Soonkyum Kim, Subhrajit Bhattacharya, Robert Ghrist and Vijay Kumar, "Topological Exploration of Unknown and Partially Known Environments", In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Tokyo, Japan, November 3-7, 2013. [DOI: 10.1109/IROS.2013.6696907]. (BibTeX)
    [   PDF  |  video  |  conference site  ]
  11. Soonkyum Kim, Subhrajit Bhattacharya and Vijay Kumar, "Path Planning for a Tethered Mobile Robot", In Proceedings of IEEE International Conference on Robotics and Automation (ICRA). Hong Kong, China, May 31 - June 7, 2014. (BibTeX)
    [   PDF  ]
  12. Soonkyum Kim, Koushil Sreenath, Subhrajit Bhattacharya and Vijay Kumar, "Trajectory Planning for Systems with Homotopy Class Constraints", In 13th International Symposium on Advances in Robot Kinematics (ARK). Innsbruck, Austria, Springer, Netherlands, jun, pages 83-90, 2012. (BibTeX)
  13. Vijay Govindarajan, Subhrajit Bhattacharya and Vijay Kumar, "Human-Robot Collaborative Topological Exploration for Search and Rescue Applications", [Nominated for Best Paper Award]. In International Symposium on Distributed Autonomous Robotic Systems (DARS)., 2014. (BibTeX)
    [  PDF  ]

Topological Abstraction for Complexity Reduction

We use various topological invariants to classify configurations of systems into equivalent classes such that the dimensionality, and hence the complexity, of the system is reduced due to the classification, yet properties such as optimality and algorithmic completeness can be guaranteed even when planning motion in the reduced (quotient) space. Homotopy and homology are useful in classifying trajectories or configuration of flexible cables. More involved constructions such as Reeb graphs are necessary for systems such as robotic arm/manipulator. Sheaf cohomology is likewise useful for joint configuration space of multiple pursuers trying to persistently surveil an environment.

[ + ]   Representative Publications
  1. Subhrajit Bhattacharya, "A General Continuous Inverse Kinematics Algorithm for a Planar Robot Arm", [Excerpts from full publication entitled "A Classification of Configuration Spaces of Planar Robot Arms with Application to a Continuous Inverse Kinematics Problem" ]. Electronic Pre-print, September, 2013-14. (BibTeX)
  2. Subhrajit Bhattacharya, David Lipsky, Robert Ghrist and Vijay Kumar, "Invariants for Homology Classes with Application to Optimal Search and Planning Problem in Robotics", Annals of Mathematics and Artificial Intelligence (AMAI), 67(3):251-281, Springer, March, 2013. DOI: 10.1007/s10472-013-9357-7. (BibTeX)
  3. Subhrajit Bhattacharya, Maxim Likhachev and Vijay Kumar, "Identification and Representation of Homotopy Classes of Trajectories for Search-based Path Planning in 3D", [Original title: Identifying Homotopy Classes of Trajectories for Robot Exploration and Path Planning] [Winner of Best Paper Award]. In Proceedings of Robotics: Science and Systems. 27-30 June, 2011. (BibTeX)
  4. Subhrajit Bhattacharya and Mihail Pivtoraiko, "A Classification of Configuration Spaces of Planar Robot Arms for a Continuous Inverse Kinematics Problem", Acta Applicandae Mathematicae, 139(1):133-166, Springer, October, 2015. DOI: s10440-014-9973-1. (BibTeX)
  5. Subhrajit Bhattacharya and Robert Ghrist, "Path Homotopy Invariants and their Application to Optimal Trajectory Planning", electronic pre-print, 2017. arXiv:1710.02871 [cs.RO]. (BibTeX)
  6. Subhrajit Bhattacharya and Robert Ghrist, "Path Homotopy Invariants and their Application to Optimal Trajectory Planning", In Proceedings of IMA Conference on Mathematics of Robotics (IMAMR). St Anne's College, University of Oxford, September 9-11, 2015. (BibTeX)
    [  PDF  |  conference website  ]
  7. Rattanachai Ramaithitima, Mickey Whitzer, Subhrajit Bhattacharya and Vijay Kumar, "Automated Creation of Topological Maps in Unknown Environments Using a Swarm of Resource-Constrained Robots", In Proceedings of IEEE International Conference on Robotics and Automation (ICRA). May 16-21, 2016. (BibTeX)
  8. Rattanachai Ramaithitima, Siddharth Srivastava, Subhrajit Bhattacharya, Alberto Speranzon and Vijay Kumar, "Hierarchical Strategy Synthesis for Pursuit-Evasion Problems", In Proceedings of the European Conference on Artificial Intelligence (ECAI). 29 August - 2 Sept, 2016. (BibTeX)

Topological Representations and Algorithms for Robot Swarms in Unknown, GPS-denied Environments

In this project we are looking into the problem of representing unknown environments without global localization (GPS-denied) using swarms of limited-capability robots and/or sparsely placed landmark sensors. The application of this research includes mapping of remote, unknown environments, deploying resources in them, and persistent surveillance of such environments.

[ + ]   Representative Publications
  1. Rattanachai Ramaithitima, Mickey Whitzer, Subhrajit Bhattacharya and Vijay Kumar, "Sensor Coverage of Unknown Environments by Robot Swarms Using Limited Local Sensing", In Proceedings of IEEE International Conference on Robotics and Automation (ICRA). May 26-30, 2015. (BibTeX)
  2. Rattanachai Ramaithitima, Mickey Whitzer, Subhrajit Bhattacharya and Vijay Kumar, "Automated Creation of Topological Maps in Unknown Environments Using a Swarm of Resource-Constrained Robots", In Proceedings of IEEE International Conference on Robotics and Automation (ICRA). May 16-21, 2016. (BibTeX)
  3. Rattanachai Ramaithitima, Mickey Whitzer, Subhrajit Bhattacharya and Vijay Kumar, "Automated Creation of Topological Maps in Unknown Environments Using a Swarm of Resource-Constrained Robots", IEEE Robotics and Automation Letters (RA-L), 1(2):746-753, January, 2016. DOI: 10.1109/LRA.2016.2523600. (BibTeX)
  4. Rattanachai Ramaithitima, Siddharth Srivastava, Subhrajit Bhattacharya, Alberto Speranzon and Vijay Kumar, "Hierarchical Strategy Synthesis for Pursuit-Evasion Problems", In Proceedings of the European Conference on Artificial Intelligence (ECAI). 29 August - 2 Sept, 2016. (BibTeX)

Simplicial Methods in Robot Motion Planning

We are developing analogs of graph search algorithms for finding shortest paths in simplicial complexes. Very often (for example, in optimal motion planning in flows) the shortest path problem can be posed in form of a differential equation. For such problems we are using a finite element-type methods on a simplicial complex representation of the environments in order to solve the differential equations and compute optimal paths.

[ + ]   Representative Publications
  1. Subhrajit Bhattacharya, "A Search Algorithm for Simplicial Complexes", Electronic Pre-print, August, 2016. arXiv:1607.07009 [cs.DM]. (BibTeX)

Research Projects

short URL: