On Targeted Complexity of Discrete Motion

Abstract

In this paper, we study targeted simplicial complexity $TC(K,L)$ introduced for situations where the configuration space possesses a simplicial structure $K$ together with a set of configurations $L$ as the target of motion. This type of complexity admits smaller values than the discrete version $TC(K)$. We then demonstrate that targeted simplicial complexity is strongly homotopy invariant and it varies between simplicial LS-categories of $K$ and $K\prod K$. Utilizing this information, we calculate targeted simplicial complexity for cases such as strongly collapsible complexes being equal to zero and for categoriacl subcomplex $L$, $TC(K,L)=scat(K)$. Moreover, we compare targeted simplicial complexity with relative topological complexity getting $TC(|K|,|L|)\le TC(K,L)$ where $|\cdot |$ denotes the geometric realization functor, and they are equal in certain cases, such as arbitrary wedges of triangulated circles. Also we define targeted $m$-step simplicial complexity of motions $T{C}_m(K,L)$ by using $m$-paths, paths whose length is smaller than or equal to $m$, to solve the problems of motion where the robot needs to be charged or repaired after $m$-steps. For $m$-step simplicial complexity a new invariance holds, which we call $m$-homotopy invariance introduced by $m$-paths. Finally we compare targeted $m$-step simplicial complexity with $m$-simplicial category $Sca{t}_m$ to obtain some lower and upper bounds and then we prove the sequence of inequalities $sca{t}_m(K)\le T{C}_m(K,L)\le T{C}_m(K)\le sca{t}_{[\frac{m}{2}]}(K\prod K)$.