I have a problem that I think can be casted in the following way.

Suppose I have a simple closed polygon $\mathcal{P}$ and $n$ squares (bounding boxes) $\mathcal{B}_1, \ldots, \mathcal{B}_n$, you can think of these bounding boxes as robot who can move in the interior of the polygon. Each box $\mathcal{B}_i$ lies inside $\mathcal{P}$, they can both rotate and traslate (so they have free parameters $x_i, y_i, \theta_i$, also assume there's at least one choice of the parameters $x_1,y_i,\theta_1,\ldots, x_n,y_n,\theta_n$ such that $\mathcal{B}_i \cap \mathcal{B}_j = \emptyset$ for each $i \neq j$.

My problem would be to find/describe all possible configurations such that this is true they never intersect.

The closest thing I managed to find is the computation of the configuration space, but I only have a reference for a single robot.

Is there any algorithm or library that would allow given the polygon and all the free robots to compute the configuration space?

PS. I'm assuming the interior of the polygon is a subset of $\mathbb{E}^2$, and $\mathcal{P}$ isn't necesserely convex.

What I'm asking is either some known algorithm to do this or a free library that can compute this for me. Or alternatively I can reuse the single robot case to compute the configuration space of the whole system (because I would assume this is possible).

Also I'm not interested in the path planning, but just the configuration space.

My current statement of the problem is the following I want to find a representation of the polytope

$$ \mathcal{C} = \left\{(x_1,y_1,\theta_1, \ldots, x_n, y_n, \theta_n) : \mathcal{B}_i(x_i,y_i,\theta_i) \subset \mathcal{P}^\circ, i =1,\ldots,n, \;\mathcal{B}_i(x_i,y_i,\theta_i) \cap \mathcal{B}_j(x_j,y_j,\theta_j) = \emptyset, 1 \leq i < j \leq n \right\} $$

Which, I think, can be factored as

$$ \mathcal{C} = \left( \prod_{i=1}^n \left\{ (x_i,y_i,\theta_i) : \mathcal{B}_i(x_i,y_i,\theta_i) \subset \mathcal{P}^\circ \right\} \right) \cap \left( \bigcap_{1 \leq i < j \leq n} \left\{ (x_1,y_1,\theta_1, \ldots, x_n, y_n, \theta_n) : \mathcal{B}_i(x_i,y_i,\theta_i) \cap \mathcal{B}_j(x_j,y_j,\theta_j) = \emptyset \right\} \right) $$

Which means the problem can be decomposed into classic configuration space computation, the only set I'm not entirely sure of is

$$ \left\{ (x_1,y_1,\theta_1, \ldots, x_n, y_n, \theta_n) : \mathcal{B}_i(x_i,y_i,\theta_i) \cap \mathcal{B}_j(x_j,y_j,\theta_j) = \emptyset \right\} $$

Which resemble to me the computation of a configuration space with a robot and an obstacle, however the obstacle can freely move around so I'm not sure how to compute the configuration space in this case.

  • $\begingroup$ I think your approach to this problem is a way too general, and you will hardly find any library to generate the configuration space for you. A more practical approach would be to design a data structure with a set of well defined operations on it - for example, return a distance the box $i$ can be moved in direction $\alpha$ until an obstacle is reached etc. $\endgroup$ – HEKTO Aug 22 '19 at 23:11
  • $\begingroup$ Apart from software libraries I'd like to know if there's any literature on the problem. I understand working in workspace to a certain extend might be useful, but honestly I find it a bit cumbersome. $\endgroup$ – user8469759 Aug 23 '19 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.