Schedule for: 20w5194 - Topological Complexity and Motion Planning (Online)

We introduce and study a new concept of parameterised topological complexity, a topological invariant motivated by the motion planning problem of robotics. In the parametrised setting, a motion planning algorithm has high degree of universality and flexibility, it can function under a variety of external conditions (such as positions of the obstacles etc). We explicitly compute the parameterised topological complexity of obstacle-avoiding collision-free motion of many particles (robots) in 3-dimensional space. Our results show that the parameterised topological complexity can be significantly higher than the standard (non-parametrised) invariant. Joint work with Daniel Cohen and Shmuel Weinberger.

Please turn on your cameras for the "group photo" -- a screenshot in Zoom's Gallery view.

Homotopic distance as introduced by Macias-Virgos and Mosquera-Lois in [2] can be realized as a generalization of topological complexity (TC) and Lusternik Schnirelmann category (cat). In this talk, we will introduce a simplicial analog (in the sense of Gonzalez in [1]) of homotopic distance and show that it has a relation with simplicial complexity (SC) as homotopic distance has with TC. We will also introduce some basic properties of simplicial distance.

[1] J. Gonzalez, Simplicial Complexity: Piecewise Linear Motion Planning in Robotics, New York Journal of Mathematics 24 (2018), 279-292.

[2] E. Macias-Virgos, D. Mosquera-Lois, Homotopic Distance between Maps, preprint. arXiv: 1810.12591v2.

A long tradition in robotics has deployed dynamical systems as “reactive” motion planners by encoding goals as attracting sets and obstacles as repelling sets of vector fields arising from suitably constructed feedback laws [1] . This raises the prospects for a topologically informed notion of “closed loop” planning complexity [2], holding substantial interest for robotics, and whose contrast with the original “open loop” notion [3] may be of mathematical interest as well. This talk will briefly review the history of such ideas and provide context for the next three talks which discuss some recent advances in the closed loop tradition, reviewing the implications for practical robotics as well as associated mathematical questions.

[1] D. E. Koditschek and E. Rimon, “Robot navigation functions on manifolds with boundary,” Adv. Appl. Math., vol. 11, no. 4, pp. 412–442, 1990, doi: doi:10.1016/0196-8858(90)90017-S.

[2] Y. Baryshnikov and B. Shapiro, “How to run a centipede: a topological perspective,” in Geometric Control Theory and Sub-Riemannian Geometry, Springer International Publishing, 2014, pp. 37–51.

[3] M. Farber, “Topological complexity of motion planning,” Discrete Comput. Geom., vol. 29, no. 2, pp. 211–221, 2003.

A recent advance in vector field methods of motion planning for robotics replaced the need for perfect a priori information about the environment’s geometry [4] with a real-time, “doubly reactive” construction that generates the vector field as well as its flow at execution time – directly from sensory inputs – but at the cost of assuming a geometrically simple environment [5] . Still more recent developments [6] have adapted to this doubly reactive online setting the original offline deformation of detailed obstacles into their geometrically simple topological models [7] . Consequent upon these new insights and algorithms, empirical navigation can now be achieved in partially unknown unstructured physical environments by legged robots, with formal guarantees that ensure safe convergence for simpler, wheeled mechanical platforms [8] . These ideas can be extended to cover a far broader domain of robot task planning [9] wherein the robot has the job of rearranging objects in the world by visiting, grasping, moving them [10] and then repeating as necessary until the rearrangement task is complete.

[4] D. Koditschek and E. Rimon, “Exact robot navigation using artificial potential functions,” IEEE Trans Robot Autom., vol. 8, pp. 501–518, 1992.

[5] O. Arslan and D. E. Koditschek, “Sensor-based reactive navigation in unknown convex sphere worlds,” Int. J. Robot. Res., vol. 38, no. 2–3, pp. 196–223, Mar. 2019, doi: 10.1177/0278364918796267.

[6] V. Vasilopoulos and D. E. Koditschek, “Reactive Navigation in Partially Known Non-convex Environments,” in Algorithmic Foundations of Robotics XIII, Cham, 2020, vol. 14, pp. 406–421, doi: 10.1007/978-3-030-44051-0_24.

[7] E. Rimon and D. E. Koditschek, “The construction of analytic diffeomorphisms for exact robot navigation on star worlds,” Trans. Am. Math. Soc., vol. 327, no. 1, pp. 71–116, 1991.

[8] V. Vasilopoulos et al., “Reactive Semantic Planning in Unexplored Semantic Environments Using Deep Perceptual Feedback,” IEEE Robot. Autom. Lett., vol. 5, no. 3, pp. 4455–4462, Jul. 2020, doi: 10.1109/LRA.2020.3001496.

[9] V. Vasilopoulos, W. Vega-Brown, O. Arslan, N. Roy, and D. E. Koditschek, “Sensor-Based Reactive Symbolic Planning in Partially Known Environments,” in 2018 IEEE International Conference on Robotics and Automation (ICRA), May 2018, pp. 1–5, doi: 10.1109/ICRA.2018.8460861.

[10] V. Vasilopoulos, T. T. Topping, W. Vega-Brown, N. Roy, and D. E. Koditschek, “Sensor-Based Reactive Execution of Symbolic Rearrangement Plans by a Legged Mobile Manipulator,” in 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Oct. 2018, pp. 3298–3305, doi: 10.1109/IROS.2018.8594342.

Hybrid dynamical systems have emerged from the engineering literature as an interesting new class of mathematical objects that intermingle features of both discrete time and continuous time systems. In a typical engineering setting, a hybrid system describes the evolution of states driven into different physical modes by events that may be instigated by an external controller or simply imposed by the natural world. Extending the formal convergence and safety guarantees of the original omniscient reactive systems introduced in the first talk of this series to the new imperfectly known environments negotiated by their doubly reactive siblings introduced in the second talk requires reasoning about hybrid dynamical systems wherein each new encounter with a different obstacle triggers a reset of the continuous model space [11]. A recent categorical treatment [12] of robot hybrid dynamical systems [13] affords a method of hierarchical composition, raising the prospect of further formal extensions that might cover as well the more broadly useful class of mobile manipulation tasks assigned to dynamically dexterous (e.g., legged) robots.

[11] V. Vasilopoulos, G. Pavlakos, K. Schmeckpeper, K. Daniilidis, and D. E. Koditschek, “Reactive Navigation in Partially Familiar Non-Convex Environments Using Semantic Perceptual Feedback,” Rev., p. (under review), 2019, [Online]. Available: https://arxiv.org/abs/2002.08946.

[12] J. Culbertson, P. Gustafson, D. E. Koditschek, and P. F. Stiller, “Formal composition of hybrid systems,” Theory Appl. Categ., no. arXiv:1911.01267 [cs, math], p. (under review), Nov. 2019, Accessed: Nov. 24, 2019. [Online]. Available: http://arxiv.org/abs/1911.01267.

[13] A. M. Johnson, S. A. Burden, and D. E. Koditschek, “A hybrid systems model for simple manipulation and self-manipulation systems,” Int. J. Robot. Res., vol. 35, no. 11, pp. 1354--1392, Sep. 2016, doi: 10.1177/0278364916639380.

A theory of topological dynamics for hybrid systems has recently begun to emerge [14]. This talk will discuss this theory and, in particular, explain how suitably restricted objects in the formal category introduced in the third talk of this series can be shown to admit a version of Conley’s Fundamental Theorem of Dynamical Systems. This raises the hope for a more general theory of dynamical planning complexity that might bring mathematical insights from both the open loop [3] and closed loop [2] tradition to the physically ineluctable but mathematically under-developed class of robot hybrid dynamics [13].

[2] Y. Baryshnikov and B. Shapiro, “How to run a centipede: a topological perspective,” in Geometric Control Theory and Sub-Riemannian Geometry, Springer International Publishing, 2014, pp. 37–51.

[3] M. Farber, “Topological complexity of motion planning,” Discrete Comput. Geom., vol. 29, no. 2, pp. 211–221, 2003.

[13] A. M. Johnson, S. A. Burden, and D. E. Koditschek, “A hybrid systems model for simple manipulation and self-manipulation systems,” Int. J. Robot. Res., vol. 35, no. 11, pp. 1354--1392, Sep. 2016, doi: 10.1177/0278364916639380.

[14] M. D. Kvalheim, P. Gustafson, and D. E. Koditschek, “Conley’s fundamental theorem for a class of hybrid systems,” ArXiv200503217 Cs Math, p. (under review), May 2020, Accessed: May 31, 2020. [Online]. Available: http://arxiv.org/abs/2005.03217.

We introduce the topological complexity of the work map associated to a robot system. In broad terms, this measures the complexity of any algorithm controlling, not just the motion of the configuration space of the given system, but the task for which the system has been designed. From a purely topological point of view, this is a homotopy invariant of a map which generalizes the classical topological complexity of a space. Joint work with Aniceto Murillo.

1. What is the $TC$ of a wedge?

In the literature one can find two relatively coarse estimates of $TC(X\vee Y)$: Farber [2] states that $$\max\{TC(X),TC(Y)\} \le TC(X\vee Y)\le \max\{TC(X),TC(Y), cat(X)+cat(Y)-1\}$$ (where the proof of the upper bound is only sketched), while Dranishnikov [1] gives $$\max\{TC(X),TC(Y), cat(X\times Y)\} \le TC(X\vee Y)\le TC(X)+TC(Y)+1.$$ At first sight the two estimates almost contradict each other, because the overlap of the two intervals is very small. Nevertheless, all known examples satisfy both estimates. We will show that under suitable assumptions Dranishnikov's method yields a proof of Farber's upper bound.

2. What can be said about closed manifolds with small TC?

If $M$ is a closed manifold with $TC(M)=2$, then by Grant, Lupton and Oprea [3] $M$ is homeomorphic to an odd-dimensional sphere. We will make another step and study closed manifolds whose topological complexity is equal to 3.

Of course, all spaces considered are CW-complexes and $TC(\mathbf{\cdot})=1$.

[1] A. Dranishnikov. Topological complexity of wedges and covering maps. Proc. AMS 142, 2014, 4365-4376.

[2] M. Farber, Topology of robot motion planning. Morse theoretic methods in nonlinear analysis and in symplectic topology, NATO Sci.Ser.II, Math.Phys.Chem., vol. 217, Springer, Dordrecht, 2006.

[3] M. Grant, G. Lupton, J. Oprea, Spaces of topological complexity one. Homology, Homotopy and Applications, 15, 2013, 73-61.

We show that the invariant topological complexity defines a new numerical invariant for orbifolds.

Orbifolds may be described as global quotients of spaces by compact group actions with finite isotropy groups. The same orbifold may have descriptions involving different spaces and different groups. We say that two actions are Morita equivalent if they define the same orbifold. Therefore, any notion defined for group actions should be Morita invariant to be well defined for orbifolds.

We use the homotopy invariance of equivariant principal bundles to prove that the equivariant A-category of Clapp and Puppe is invariant under Morita equivalence. As a corollary, we obtain that both the equivariant Lusternik-Schnirelmann category of a group action and the invariant topological complexity are invariant under Morita equivalence. This allows a definition of topological complexity for orbifolds.

This is joint work with Andres Angel, Mark Grant and John Oprea

I will present a new kind of integer-valued homotopy invariants of topological spaces, which allow for a Lusternik-Schnirelmann-type approach to counting critial orbits of G-invariant functions on subspaces of C^0(S^n,X). Here, G is a closed subgroup of O(n+1) acting on C^0(S^n,X) by reparametrization. These invariants, so-called spherical complexities, are sectional categories of fibrations generalizing topological complexity. I will explain how to obtain lower bounds for them using sectional category weights of cohomology classes and how to find suitable classes of higher weight. Moreover, I will present some consequences of the method for the topological complexity of manifolds. As an application, I will outline how to derive new existence results for closed geodesics of Finsler metrics of positive flag curvature on spheres. Closed geodesics are given as the critical points of the SO(2)-invariant energy functional of the Finsler metrics on a Hilbert manifold of free loops, thus well-suited to our approach.

Exponential generating functions for Euler characteristics of exotic configuration spaces have a remarkably simple representation in terms of the local geometry of the underlying spaces.

We will discuss the proof of the equality TC(G)=2cd(G) for nonabelian hyperbolic groups

The topological complexity TC(X) of a space X was introduced in 2003 by Farber to measure the instability of robot motion planning in X. The motion is not required to be along shortest paths in that setting. We define a new version of topological complexity in which we require the robot to move along shortest paths (more specifically geodesics), which we call the geodesic complexity GC(X). In order to study GC(X) we introduce the total cut locus.

We show that the geodesic complexity is sensitive to the metric and in general differs from the topological complexity, which only depends on the homotopy type of the space. We also show that in some cases both numbers agree. In particular, we construct the first optimal motion planners on configuration spaces of graphs along shortest paths (joint work with Donald Davis and Michael Harrison).

The $TC$-generating function associated to a space $X$ is the formal power series $\mathcal{F}_X(x) = \sum_{r=1}^\infty TC_{r+1}(X)\,x^r.$ For many examples $X$, it is known that $\mathcal{F}_X(x)= \frac{P_X(x)}{(1-x)^2},$ where $P_X(x)$ is a polynomial with $P_X(1)=cat(X)$. Is this true in general? I shall discuss recent developments concerning this question, including observing that the answer is related to $X$ satisfying logarithmicity of LS-category. Also, in the examples mentioned above, it is always the case that $P_X(x)$ has degree less than or equal to $2$. Is this true in general? I shall discuss this question in the context of right-angled Artin (RAA) groups and along the way see how RAA groups yield some interesting byproducts for the study of $TC$.

We define the notion of near geodesic between points where no geodesic exists, and use this to define geodesic complexity for non-geodesic spaces. We determine explicit near geodesics and geodesic complexity in a variety of cases.