Wednesday, June 29, 2005

Paper: Distributed Control for 3D Metamorphosis

Paper link

Useful comments
Metamorphic robot systems

Homegenity of modules Advantages: Robustness , adaptability and mass production

Challenge for dist systems for self reconfig is that each module must decide its next move based on the desired final configuration and only its local state , which includes delayed or incomplete global information obtained via communication from other modules

Important Related work
Motion planning: Simulated annealing techniques to drive the reconfig process.
Distributed control: disitrbuted sim annealing approach
Approach of meta modules à treat multiple modules as one and move them together

Emergent structures: another interesting approach : final config is not prespecified but emerges as local rules are applied to the catoms. The specific shape is undeterministic , the emergent structure has some desired functionality.

Key Ideas
Goal ordering:the main idea in the paper
The paper gives an ordering of all the neighbouring empty sites which should be filled as part of the final configuration. The modules them move into the neighouring sites in increasing order.
Ordered goal constraints. Empty Locations in the final goal are filled in a predefined globally known partial order. à introduces monotoicity and stability of the system

Three algorithms are developed based on “ordered-goal” constraint.
a. One is distance based where modules move towards closed unfulfilled goal.
b. Heat based à simulate a heat flow from goal targets to modules along the temperature gradient
c. Hybrid of these two.

Motion constraints
This paper has an indepth discussion and formal. of motion constraints. Main ones are blocking constraints, connectivity constraints and fixed base constraint: one of the modules remains fixed during the entire re-config.

The problem: two different types
Motion planning and motion control problems
Motion planning: given I and F , output all the single steps that lead from I to F. (centr. Approach)
Motion control: give current config, F and current state, output a single step that moves towards final configuration
A hybrid of two also works

Module capabilities assumed (and prob required also in the simulator)
Nice discussion of catom capabilities required for distributed control: Each catom decides where to move based on : 1. current site 2. its current state 3. state of neighbors (from local communicatin) 4. Each catom also has limited sensing to determine collision and disconnection detection

Some specific issues faced in distributed control
Stability, Local Minima, overcrowding (hindering further movement)

The way movement happens:

There are three phases:
1. Reset phase : like a barrier in parallel comm.: all catoms come in sync
2. Communication phase: All modules communicate about their current positions and state
3. Decision phase: decide where to move

Goal Ordering

Two methods to reach unfulfilled goal positions ( sites which need to be filled to reach the global specified structure):
a. distance based method: Euclidean distance
b. heat based method: empty sites near to goals are given higher temperature. High temperature vacant positions are given higher priority.

They use the methods to make different shapes like falt disk, solid ball, hollow ball and cup. The time required is linear in the number of modules , which is pretty good.

Other Future ideas

Decompose a shape into a set of simple ones , design reconfiguration algorithms for each simple shape and then recombine the steps.


Post a Comment

<< Home