On the motion planning problem, complexity, entropy, and nonholonomic interpolation (Q867468)

A general motion planning problem from robotics is defined by a triple \((\Delta, \, g, \, \Gamma)\) which consists of: 1 a distribution \(\Delta\) over \(\mathbb{R}^{n}\) of a certain co-rank \(p\) which represents the admissible motion (the kinematic constrains) of the robot; 2 a Riemannian metric \(g\) over \(\Delta\) providing a sub-Riemannian metric structure \(d\) to measure the length of admissible curves; 3 a smooth non-admissible curve \(\Gamma : [0,1] \rightarrow \mathbb{R}^{n}\). The paper under review deals with the sub-Riemannian motion planning problem defined by a sub-Riemannian metric and a non-admissible curve to be \(\varepsilon\)-approximated in the sub-Riemannian sense by a trajectory of the robot. It is shown that the metric complexity \(MC\) and the entropy \(E\) characterize the \(\varepsilon\)-optimality of the approximation. The main results of the paper are as follows: a) For generic one-step bracket-generating problems, when the co-rank is at most \(3\), the entropy is related to the complexity by \(E=2 \pi MC\). b) The entropy in the special \(2\)-step bracket-generating case is computed. c) It is shown that the formula for entropy which is valid up to co-rank \(3\) changes in a wild case of co-rank \(6\): it has to be multiplied by a factor which is at most \(3/2\).