Directed topological complexity

Lyusternik-Shnirel'man category of a space, topological complexity à la Farber, topological robotics (topological aspects) (55M30) Homotopy theory (55P99) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Model systems in control theory (93C99)

Abstract: It has been observed that the very important motion planning problem of robotics mathematically speaking boils down to the problem of finding a section to the path-space fibration, raising the notion of topological complexity, as introduced by M. Farber. The above notion fits the motion planning problem of robotics when there are no constraints on the actual control that can be applied to the physical apparatus. In many applications, however, a physical apparatus may have constrained controls, leading to constraints on its potential future dynamics. In this paper we adapt the notion of topological complexity to the case of directed topological spaces, which encompass such controlled systems, and also systems which appear in concurrency theory. We study its first properties, make calculations for some interesting classes of spaces, and show applications to a form of directed homotopy equivalence.

Review text

Topological complexity \(TC(X)\), for an arbitrary topological space \(X\), was introduced by \textit{M. Farber} [Discrete Comput. Geom. 29, No. 2, 211--221 (2003; Zbl 1038.68130)]. This notion reflects the structure of motion planning algorithms for systems having \(X\) as their configuration space. To define \(TC(X)\) one considers the ``path space fibration \(\chi:X^I\rightarrow X\times X\) defined by \(\chi(p)=(p(0),p(1))\) where \(X^I\) is the space of all paths \(p:I=[0,1]\rightarrow X \) with the compact-open topology. A motion planning algorithm is a section of this ``fibration and a continuous section exists if and only if the configuration space \(X\) is contractible. Then \(TC(X)\) is defined as the minimal number of continuous ``local rules that are needed to describe a section. The topological complexity is the minimal number \(k\) such that there exists an open cover \(\{ {U}_{i=1}^{k}\}\) of \(X\times X\), such that for each \(i=1,\dots ,k\), there exists a local section \(s_{i}:U_{i}\rightarrow X^I \). Some interesting examples are given: \(TC(X) = 1\) if and only if \(X\) is contractible; \(TC(S^n)=2\) for \(n\) odd and \(TC(S^n)=2\) for \(n\) even; for a configuration space, \(PC(F(\mathbb{R}^m,n))=2n-1\) for \(m\) odd and \(PC(F(\mathbb{R}^m,n))=2n-2\) for \(m\) even, and others. These are examples in algebraic topology, where the space of all paths \(X^I\) exists for any topological space \(X\). This means that one imposes no limitations on motion of the system assuming that any continuous motion is admissible. ``In many applications, however, a physical apparatus may have constrained controls, leading to constraints on its potential dynamics. In these cases it is necessary to use the mathematics of directed algebraic topology which studies directed spaces (or d-spaces), which are topological spaces with privileged directions, and directed paths therefore do not need to be reversible. By this practical motive the notion of topological complexity is needed to be generalized or adapted for d-spaces, what the authors of this paper set out to do. The paper has 7 sections: 1. Introduction, 2. Definitions, 3. Directed topological complexity, 4. Regular d-spaces, 5. Directed graphs, 6. Higher-dimensional directed spaces, 7. Directed homotopy equivalence and topological complexity. In Section 1 concrete arguments from the field of differential equations with some control parameters are given for defining and studying a notion of complexity for d-spaces. Section 2 includes some notions, notations and results from directed topology. Thus \((X,dX)\) denotes a d-space with \(dX\subseteq X^I\). Then for a topological space \(X\) and \(D\) a set of paths \(p:I\rightarrow X\) closed under concatenation and such that the union of the images \(p(I)\), for \(p\in D\), is \(X\), the smallest set of paths containing \(D\), denoted by \(\overline{D}\), is a d-structure on \(X\), which is called the saturation of \(D\). The saturation \(\overline{D}\) is made of all composites of paths of \(D\) with continuous and non-decreasing maps \(I\rightarrow I\). In the same section examples are given of d-spaces in control theory and in concurrency and distributed systems theory. Then, given a d-space \((X,dX)\), the authors define the paths-map by \(\chi:dX\rightarrow X\times X\) with \(\chi(p)=(p(0),p(1))\) where \(p\in dX\). The image of \(\chi\) is a subset of \(X\times X\), denoted \(\Gamma_X=\{(x,y)\in X\times X\mid \exists p\in dX, p(0)=x,p(1)=y\}\). Finally, for \( a,b \in X\), the symbol \(dX(a,b)\) denotes the subspace of \(dX\) consisting of all d-paths starting at \(a\in X\) and ending at \(b \in X\). By \(\ast\) is denoted the concatenation map \(dX(a,b)\times dX(b,c)\rightarrow dX(a,c)\) and \(dX(a,b)\) is nonempty if and only if \((a,b)\in \Gamma_X\). Section 3 is the core of the paper. \textsl{Directed topological complexity} \(\overrightarrow{TC}(X,dX)\) of a d-space \((X,dX)\) is defined as the minimum number \(n\) (or \(\infty\) if no such \(n\) exists) such that there exists a map \(s:\Gamma_X\rightarrow dX\) (not necessarily continuous) and \(\Gamma_X\) can be partitioned into \(n\) ENRs spaces \(\Gamma_X=F_1\cup F_2\cup\dots\cup F_n\) , \(F_i\cap F_j=\emptyset\), \(i\neq j\), such that: (i) \( \chi \circ s = Id\) , i.e. \(s\) is a (non-necessarily continuous) section of \(\chi\), and (ii) \(s|F_i:F_i\rightarrow dX\) is continuous. A collection of such ENRs, \(F_1,\dots, F_n\) , with \(n\) equal the directed topological complexity of \((X,dX)\), is called a patchwork. Several examples are given: in control theory, in concurrency and distributed systems theory \(\overrightarrow{TC}(I)=1\), \(\overrightarrow{TC}(\overrightarrow{S^1})\) =2. Section 4. A d-space \((X,dX)\) is called regular if one can find a partition \(\Gamma_X=F_1\cup F_2\cup\dots\cup F_n\), \(n=\overrightarrow{TC}(X,dX)\) into ENRs such that the map \(\chi\) admits a continuous section over each \(F_i\) and, additionally, the \(\cup_j^r F_j\) are closed for any \(r=1,\dots,n\) . This implies \(\overline{F_i}\cap F_{i'}=\emptyset\), for \(i<i'\), which in the case of the ``undirected theory is automatically satisfied. The directed circle \(\overrightarrow{S^1}\) is regular. If \((X_i,dX_i)\) are regular for \(i=1,\dots,k\) , then \(\overrightarrow{TC}(X_1\times \cdots\times X_k)-1\leq \sum_{i=1}^k[\overrightarrow{TC}(X_i)-1]\). As an example for this proposition the directed torus \((\overrightarrow{S^1})^n\) satisfies \(\overrightarrow{TC}((\overrightarrow{S^1})^n)\leq n+1\) . A d-space \((X,dX)\) is called strongly connected if \(\Gamma_X=X\times X\) and for such a d-space \(TC(X)\leq \overrightarrow{TC}(X,dX)\). As an example, the directed loop \(\mathbb{O}^1\) has \(\overrightarrow{TC}(\mathbb{O}^1)=2\) and it is regular; and \(\overrightarrow{TC}((\mathbb{O}^1)^n)=n+1\). In Section 5 two propositions are proved regarding \(\overrightarrow{TC}(G)\) for \(G\) a directed connected graph, i.e. each edge of \(G\) has a specified orientation. For such a directed space \(G\), \(\overrightarrow{TC}(G)\leq 3\) and if \(G\) is a strongly connected directed graph, then \(\overrightarrow{TC}(G)=TC(G)=min(b_1(G),2)+1\), where \(b_1(G)\) is the first Betti number of the graph \(G\). In Section 6 the authors study so called cubical complexes, particularly the hypercube \(\Box^n\) and directed sphere \(\overrightarrow{\mathbb{S}^n}=\partial \Box^{n+1}\), \(\overrightarrow{TC}(\overrightarrow{\mathbb{S}^n})=2\) for any \(n\geq 1\). For a directed disc \(D^2\), for which \(TC(D^2)=1\), it is proved that \(\overrightarrow{TC}(D^2)=2\). And very interesting, there exists a directed space \((X,dX)\) with \(TC(X)=2\) and \(\overrightarrow{TC}(X,dX)=1\). In Section 7 it is proved that if \((X,dX)\) and \((Y,dY)\) are two simply dihomotopy equivalent d-spaces, then \(\overrightarrow{TC}(X,dX)=\overrightarrow{TC}(Y,dY)\). Particularly, if \(X\) is a contractible d-space, then the dipath space map has a continuous section if and only if \(X\) is dicontractible i.e., it is basic dihomotopy equivalent to a point. As an example it is proved: that the directed \(n\)-tori \((\mathbb{O}^1)^n\) and \((\mathbb{O}^1)^m\) cannot be basic dihomotopy equivalent when \(n\neq m\), and \(n\)-tori \((\mathbb{O}^1)^n\) cannot be basic dihomotopy equivalent to any directed graph for \(n\geq 3\). The last result is a proposition on the natural homologies \(\overrightarrow{H}_n(X)\) of a d-space \(X\) with \(TC(X)=1\).

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Directed topological complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2304014)