1# Quotient Space Planning Framework {#quotientSpacePlanning} 2 3[TOC] 4 5We use the Quotient Space Planning Framework to formalize planning on different abstractions levels. 6Abstraction levels are defined as [QuotientSpaces](https://en.wikipedia.org/wiki/Quotient_space_(topology)) which are lower-dimensional abstractions of the configuration space. 7A simple example is a rigid body in the plane with the configuration space \f$SE(2)\f$. 8We can abstract this configuration space by projecting onto \f$\mathbb{R}^2\f$, the QuotientSpace of positions of the rigid body. 9 10## Admissible QuotientSpace Projections 11 12QuotientSpace projections are many-to-one mappings, which map subsets of the 13configuration space to a point of a QuotientSpace. The QuotientSpace, as the 14configuration space, contains feasible and infeasible configurations. We like to 15disallow projections which map feasible configurations onto infeasible 16Quotientspace configurations --- because we could thereby abstract away valid 17feasible paths. 18 19A QuotientSpace projection thus projects an infeasible subset onto an infeasible 20point, but never a feasible configuration onto an infeasible configuration. Such 21projection are called admissible. 22 23For the rigid body example, we get an admissible projection by nesting a smaller 24robot in the larger one. Below we show a simple planning problem, where a rigid 25body needs to move from an initial start configuration (green) to a designated 26goal configuration (red). This problem can be abstracted by nesting a disk in 27the rigid body (right Figure). 28 29\htmlonly 30<div class="row"> 31 <img src="images/quotient/rigidbody2d_1.png" class="col-xs-6 col-xs-offset-3"> 32 <img src="images/quotient/rigidbody2d_2.png" class="col-xs-6 col-xs-offset-3"> 33</div> 34</div> 35\endhtmlonly 36 37The same can be done to any robot. To abstract a 3-dof manipulator (Left Figure), one could remove the last link to obtain a 2-dof manipulator (Right Figure) which corresponds to a QuotientSpace projection from a 3-dimensional space to a 2-dimensional space. 38 39\htmlonly 40<div class="row"> 41 <img src="images/quotient/planar_manipulator_3dofs.png" class="col-xs-6 col-xs-offset-3"> 42 <img src="images/quotient/planar_manipulator_2dofs.png" class="col-xs-6 col-xs-offset-3"> 43</div> 44</div> 45\endhtmlonly 46 47In practice, an admissible projection requires that any constraint on the 48QuotientSpace is also a constraint on the ConfigurationSpace or any 49high-dimensional QuotientSpace. In that sense, QuotientSpace projections are 50similar to constraint relaxations. 51 52## Spurious Paths 53 54Our main problem when planning with QuotientSpaces are spurious paths. A 55spurious path is a path on a quotient space which cannot be lifted to the 56configuration space (A QuotientSpace path can be lifted iff there exists a 57feasible path on the ConfigurationSpace which when projected onto the 58QuotientSpace will yield the QuotientSpace path). An example is shown below. On 59the left we have a solution path for the nested disk going below the obstacle. 60This solution path, however, cannot be lifted to the configuration space --- the 61L-shaped robot cannot pass below the obstacle. A feasible path on the 62ConfigurationSpace is shown on the right, which goes above the obstacle. This 63path is a projection of the feasible path on the 3-dimensional 64ConfigurationSpace down onto the 2-dimensional QuotientSpace. 65 66\htmlonly 67<div class="row"> 68 <img src="images/quotient/rigidbody2d_3.png" class="col-xs-6 col-xs-offset-3"> 69 <img src="images/quotient/rigidbody2d_4.png" class="col-xs-6 col-xs-offset-3"> 70</div> 71</div> 72\endhtmlonly 73 74## Probabilistic Completeness 75 76To plan with a sequence of QuotientSpaces, we have developed a new algorithm 77called the QuotientSpace Rapidly-exploring random tree (QRRT) algorithm. 78ompl::geometric::QRRT is probabilistically complete when used with admissible 79projections, i.e. it can solve any planning problem which has a solution. In 80particular, QRRT can deal with spurious paths. It does so by sampling random 81vertices from a lower-dimensional QuotientSpace, and projecting them into the 82configuration space. 83 84## Why Use Quotient Space Planning 85 86- Because it is more general than lower-dimensional projections like 87 ompl::base::ProjectionEvaluator: 88 - (1) We can handle a finite number of sequential projections instead of just one. 89 - (2) We can guarantee probabilistic completeness when used with admissible projections 90 - (3) We can project onto many manifold spaces instead of just euclidean 91 space \f$\mathbb{R}^N\f$. 92- Because it can be much faster compared to other planning algorithms. 93 94### Hypercube Benchmark 95 96To see how much faster QuotientSpace planning can be, we provide a hypercube 97demo, which you can run yourself using the [Quotient Space HyperCube File.](QuotientSpacePlanningHyperCube_8cpp_source.html) 98 99For demonstration, we change the number of dimensions of the hypercube from 1006 to 8 to 10 and finally to 12 (using a narrow passage 101of 0.1). 102 103#### 6-dimensional HyperCube 104 105Our results show that ompl::geometric::PRM 106performs best with 0.103 seconds and ompl::geometric::QRRT on second place 107with 0.111 seconds. 108 109~~~{.txt} 110Finished Benchmark (Runtime:10, RunCount:5) 111Placement <Rank> <Time (in Seconds)> <Success (in Percentage)> 112-------------------------------------------------------------------------------- 113Place <1> Time: <0.103107> %Success: <100> (PRM) <-- Winner 114Place <2> Time: <0.111702> %Success: <100> (QuotientSpaceRRT[3lvl]) 115Place <3> Time: <5.33306> %Success: <60> (STRIDE) 116Place <4> Time: <9.86457> %Success: <20> (RRT) 117Place <5> Time: <10.0467> %Success: <0> (KPIECE1) 118Place <6> Time: <10.069> %Success: <0> (EST) 119-------------------------------------------------------------------------------- 120~~~ 121 122#### 8-dimensional HyperCube 123 124Comparing only the two winning algorithms, we see that ompl::geometric::PRM does not scale well to 8 dimensions with zero solved runs, while ompl::geometric::QRRT performs well with 0.653 seconds for solving every single run. 125 126~~~{.txt} 127Finished Benchmark (Runtime:10, RunCount:5) 128Placement <Rank> <Time (in Seconds)> <Success (in Percentage)> 129-------------------------------------------------------------------------------- 130Place <1> Time: <0.65329> %Success: <100> (QuotientSpaceRRT[4lvl]) <-- Winner 131Place <2> Time: <10.0419> %Success: <0> (PRM) 132-------------------------------------------------------------------------------- 133~~~ 134 135#### 10-dimensional HyperCube 136 137ompl::geometric::QRRT even performs well when we increase the dimensions further to 10. 138 139~~~{.txt} 140Finished Benchmark (Runtime:10, RunCount:5) 141Placement <Rank> <Time (in Seconds)> <Success (in Percentage)> 142-------------------------------------------------------------------------------- 143Place <1> Time: <1.84356> %Success: <100> (QuotientSpaceRRT[5lvl]) <-- Winner 144-------------------------------------------------------------------------------- 145~~~ 146 147#### 12-dimensional HyperCube 148 149The algorithm comes to a limit when we increase the dimensionality further to 12. 150 151~~~{.txt} 152Finished Benchmark (Runtime:10, RunCount:5) 153Placement <Rank> <Time (in Seconds)> <Success (in Percentage)> 154-------------------------------------------------------------------------------- 155Place <1> Time: <9.11489> %Success: <20> (QuotientSpaceRRT[6lvl]) <-- Winner 156-------------------------------------------------------------------------------- 157~~~ 158 159## Want to learn more? 160 161### Tutorials 162 163Check out the [tutorial](quotientSpacePlanningTutorial.html). 164 165### Demos 166 167Check out the [demos](group__demos.html). 168 169### Papers 170 171- A Orthey and M Toussaint, _Rapidly-Exploring Quotient-Space Trees: Motion Planning using Sequential Simplifications_, 2019. Also available at <https://arxiv.org/abs/1906.01350>. 172 173- A Orthey, A Escande and E Yoshida, _Quotient Space Motion Planning_, ICRA, 2018. Also available at <https://arxiv.org/abs/1807.09468>. 174