Solving the empty space problem in robot planning by mathematical morphology

J.B.T.M. Roedernik

Workshop: Mathematical Morphology and its Applications to Signal Processing, Barcelona, 1993

Summary

                  The path planning problem is in regard of finding a path for an object moving in a space with obstacles. The problem can be divided in two subproblems: the empty space problem and the find path problem, the former which is used to find the allowed states for the robot and the latter being the definition of a specific trajectory within the results obtained from the first problem. This paper is covering the empty space issue, therefore it is not dealing with kinematics or dynamics of the system, but uses morphological operators on spaces with transitive information groups (transitive indicates that for a pair of points in a set χ acting on a group Γ, there is a transformation g∈Γ which maps one point to an other). Γ is given by translation T, while in case of rotations it become an Euclidean group M, in a multiple joint problem different Γ can describe the system. The paper introduces the basics of Minkowski Operators (page 2), for which the sum of two sets represents the union of the translations of the left addend over the vector of the right addend and the subtraction being the intersection.

Dilation and erosion are respectively two operators representing the generalized version of sum and subtraction, being both left invariant.

If χ is a non-empty set and Γ a transformation group on χ, so that g : χ à χ, then gh(x)=g(h(x)), e(x)=x, being e the unit element of Γ and gh the group element g and h; the inverse of an element g∈Γ is g^-1 and g(x) is gx, with Γ

defined as a group action on χ. If x∈Γ is defined as a stabilizer then it is a subgroup Γ_x:={ g∈Γ : gx=x}. If ⦰ is the origin, then the stabilizer Γ_⦰ = { g∈Γ : g⦰=0} is defined as Σ, a group of elements maping the origin to a given point x is defined as a left coset g_xΣ := {g_xs : s∈Σ}.

Given the properties introduce above, rotation around the origin followed by a translation is: γ_h,Φ=τ_hρ⁰_Φ, where τ_h is the translation over vector h and ρ⁰_Φ is rotation around the origin by and angle Φ.

A pointer p:=(x,v) is defined as a set of a vectors v and their common starting point x, the pointer p:=(x,v) where v=(cosΦ, sinΦ) is representing the motion of γ_x,Φ.

Two morphological operator are then introduced: lift = {g∈Γ : g⦰ ∈ X} and the canonical projection π(G)={g⦰ : g ∈ G}, where the lift is defined also as τ(X)⊕R.

·       Model

The problem is to find a set of forbidden configurations, the state of the robot is parameterized by h of an arbitrary robot B initially at the origin. In the translation problem the configuration space C coincides with the space R², so the forbidden space points are identified as: Q_B(X)={h ∈ R² : τ_hB⇑X} (where B⇑X is ‘A hits B’ and its equal to A∩B≠⦰), this is the Euclidean dilation of X by B’s reflection.

In the case of translation and rotation, considering two link connected through one joint we then divide the problem in two for each link.

We take to points from each link (P₁, P₂), considering the configuration space as C:={(h, Φ) : h ∈ R² , Φ ∈ S₁}, where h is the location of P₁ and Φ the angle of the line P₁P₂ with respect to x axis and initial state {h=(0,0),Φ=0}. The hitting function results to be Q_B(X)={ (h, Φ) ∈ C : γ_h,ΦB⇑X}, this results to be the Mikowski summation of the lift of X and the inverse lift of B.

Key Concepts

Minkowski Operator, Empty-Space Problem

Key Results

The case of a mobile robot with a finite number of joints can be solved by a combination of the cases presented above so that the final hitting can be written as a union of two M-dilations. The empty space problem can be decomposed into independent part, one for each part of the robot, being applied therefore also in 3D.