This chapter is focused on the motion coordination of a multi robot system (MRS) over a shared space. In particular, it is focused on the coordination of a team of mobile robots moving over a 2D surface in an office-like environment. The proposed approach is coherent with a layered MRS architecture, where the motion system is only a subpart of it. Besides any architectural issues, which mainly concern with the design and, therefore, with the handling of multi threads/concurrent systems, the real-time coordination of the motion of n bodies is the major problem. Typical applications include the CMOMMT problem [Parker, 1999] related to surveillance tasks, as well as cooperation issues in soccer teams (e.g., RoboCup) or transportation of parts in manufacturing plants or equivalent problems. We consider a MRS composed of mobile robots having generic shapes, sizes and different kinematics (heterogeneous team). We have developed an algorithm that computes the shortest collision-free path for each robot, from the starting multi pose (vector of n poses) to the goal multi pose, while considering their real space occupancy and avoiding collisions with static and dynamical obstacles (i.e., other robots). Though there are planners working on continuous spaces which have interesting features, they are also time consuming, a characteristic unsuitable for a real-time problem. To reduce the planning time, a discrete representation of the world (environment and robots) has been preferred. This approach is itself layered: we use a Multilayered Cellular Automata (MCA) architecture as a paradigm to formalize the propagation of potential values between adjacent 4D cells (hypercells). In particular, the MCA approach is well suited when the layers correspond to the time slices: the physical 3D Space at a given timestamp. The planner underlying mechanism is an artificial field over a lattice (CAs), where the robot has been shrunk to a point subjected to attractive and repulsive forces (Lagrangian mechanics). Building a regular 4D manifold of potential values and following its minimum valleys, a trajectory in the Spacetime is evaluated. It corresponds to a robot movement (geometrization of the motion). An important result has been stated: the potential field over the spatiotemporal domain is not conservative. The lines connecting the start and the goal Poses (a 3D pose + timestamp) over the Spacetime are not independent from them: not every geometrical solution is admissible. The dependency arises from the interaction between robots with finite shapes. The potential manifold is constructed on the base of the motion operators. These are the atomic (non interruptible) moves over the space and the time lattice. The set of all of them represents the entire kinematics of a robot. The manifold emerges from the interaction of the set of motion operators, the world model and the representation of the robots shapes. Using a discretized C Spacetime, the definition of velocity of a robot becomes an intrinsical (geometrical) property emerging from the interaction between the motion operators and the Spacetime. It is fundamental for a correct planning to take care of the actual robot occupancy during an atomic move to avoid collisions with other robots/obstacles. We derived the definition of Motion Silhouette, a conceptual evolution of the Sweeping Silhouette (Marchese 2003), which is itself an evolution of the Obstacles Enlargement concept (Lozano-Perez 1983). To avoid the problem of the positions swapping between two robots, it is very important to take into account the well-known Shannon’s Theorem in the discretization phase of the C Spacetime and, consequently, in the definition of Motion Silhouette. The overall algorithm works with polygonal obstacles (even with concavities, without stalling inside), with multiple robots with any type of kinematics (holonomic, non-holonomic, car-like, etc.) and shapes (convex, concave, with holes), planning the optimal motions of robots (even inside one another) and facing different types of problems (e.g., the choice of the best goal in a set of goals for a robot). Experimental results on a variety of planning problems indicate the feasibility and the effectiveness of the proposed approach.
Marchese, F. (2011). MRS Motion Planning: the Spatiotemporal MultiLayered Cellular Automata Approach. In D. Chugo, S. Yokota (a cura di), Introduction to Modern Robotics (pp. 229-250). Hong Kong : iConcept Press.
MRS Motion Planning: the Spatiotemporal MultiLayered Cellular Automata Approach
MARCHESE, FABIO MARIO GUIDO
2011
Abstract
This chapter is focused on the motion coordination of a multi robot system (MRS) over a shared space. In particular, it is focused on the coordination of a team of mobile robots moving over a 2D surface in an office-like environment. The proposed approach is coherent with a layered MRS architecture, where the motion system is only a subpart of it. Besides any architectural issues, which mainly concern with the design and, therefore, with the handling of multi threads/concurrent systems, the real-time coordination of the motion of n bodies is the major problem. Typical applications include the CMOMMT problem [Parker, 1999] related to surveillance tasks, as well as cooperation issues in soccer teams (e.g., RoboCup) or transportation of parts in manufacturing plants or equivalent problems. We consider a MRS composed of mobile robots having generic shapes, sizes and different kinematics (heterogeneous team). We have developed an algorithm that computes the shortest collision-free path for each robot, from the starting multi pose (vector of n poses) to the goal multi pose, while considering their real space occupancy and avoiding collisions with static and dynamical obstacles (i.e., other robots). Though there are planners working on continuous spaces which have interesting features, they are also time consuming, a characteristic unsuitable for a real-time problem. To reduce the planning time, a discrete representation of the world (environment and robots) has been preferred. This approach is itself layered: we use a Multilayered Cellular Automata (MCA) architecture as a paradigm to formalize the propagation of potential values between adjacent 4D cells (hypercells). In particular, the MCA approach is well suited when the layers correspond to the time slices: the physical 3D Space at a given timestamp. The planner underlying mechanism is an artificial field over a lattice (CAs), where the robot has been shrunk to a point subjected to attractive and repulsive forces (Lagrangian mechanics). Building a regular 4D manifold of potential values and following its minimum valleys, a trajectory in the Spacetime is evaluated. It corresponds to a robot movement (geometrization of the motion). An important result has been stated: the potential field over the spatiotemporal domain is not conservative. The lines connecting the start and the goal Poses (a 3D pose + timestamp) over the Spacetime are not independent from them: not every geometrical solution is admissible. The dependency arises from the interaction between robots with finite shapes. The potential manifold is constructed on the base of the motion operators. These are the atomic (non interruptible) moves over the space and the time lattice. The set of all of them represents the entire kinematics of a robot. The manifold emerges from the interaction of the set of motion operators, the world model and the representation of the robots shapes. Using a discretized C Spacetime, the definition of velocity of a robot becomes an intrinsical (geometrical) property emerging from the interaction between the motion operators and the Spacetime. It is fundamental for a correct planning to take care of the actual robot occupancy during an atomic move to avoid collisions with other robots/obstacles. We derived the definition of Motion Silhouette, a conceptual evolution of the Sweeping Silhouette (Marchese 2003), which is itself an evolution of the Obstacles Enlargement concept (Lozano-Perez 1983). To avoid the problem of the positions swapping between two robots, it is very important to take into account the well-known Shannon’s Theorem in the discretization phase of the C Spacetime and, consequently, in the definition of Motion Silhouette. The overall algorithm works with polygonal obstacles (even with concavities, without stalling inside), with multiple robots with any type of kinematics (holonomic, non-holonomic, car-like, etc.) and shapes (convex, concave, with holes), planning the optimal motions of robots (even inside one another) and facing different types of problems (e.g., the choice of the best goal in a set of goals for a robot). Experimental results on a variety of planning problems indicate the feasibility and the effectiveness of the proposed approach.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
