Programming for modular reconfigurable robots

Composed of multiple modular robotic units, self-reconfigurable modular robots are metamorphic systems that can autonomously rearrange the modules and form different configurations depending on dynamic environments and tasks. The goal of self-reconfiguration is to determine how to change connectivity of modules to transform the robot from the current configuration to the goal configuration subject to restrictions of physical implementation. The existing reconfiguration algorithms use different methods, such as divide-and-conquer, graph matching, and the like, to reduce the reconfiguration cost. However, an optimal solution with a minimal number of reconfiguration steps has not been found yet. The optimal reconfiguration planning problem consists in finding the least number of reconfiguration steps transforming the robot from one configuration to another. This is an NP-complete problem. In this paper, we describe an approach to solve this problem. The approach is based on constructing logical models of the problem under study.

• Publication year

  2012

• Venue

  Programming and computer software

• Publication date

  Unknown publication date

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1134/S0361768812010033
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• PROGRA~MMING AND COMPUTER SOFTWARE

  2013cited by this paper
• Swarm Intelligence

  2012cited by this paper
• Self-Reconfigurable Modular Robotic System

  2012cited by this paper
• A machine program for theorem-proving

  2011cited by this paper
• On the complexity of optimal reconfiguration planning for modular reconfigurable robots

  2010influential reference
• Heuristic Planning with SAT: Beyond Uninformed Depth-First Search

  2010cited by this paper
• Heuristics for Planning with SAT

  2010cited by this paper
• Stochastic Learning for SAT- Encoded Graph Coloring Problems

  2010cited by this paper
• Generalizing metamodules to simplify planning in modular robotic systems

  2008cited by this paper
• Distributed, dynamic, and autonomous reconfiguration planning for chain-type self-reconfigurable robots

  2008cited by this paper
• Another look at graph coloring via propositional satisfiability

  2008cited by this paper
• Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves

  2008cited by this paper
• Planning Graphs and Propositional Clause-Learning

  2008cited by this paper
• Meld: A declarative approach to programming ensembles

  2007cited by this paper
• Planning as Satisfiability with Relaxed $-Step Plans

  2007cited by this paper
• Optimal Kinodynamic Motion Planning for 2D Reconfiguration of Self-Reconfigurable Robots

  2007cited by this paper
• Exploiting hierarchy and structure to efficiently solve graph coloring as SAT

  2007cited by this paper
• Roombots : Toward Emancipation of Furniture . A Kinematics-Dependent Reconfiguration Algorithm for Chain-Type Modular Robots

  2007cited by this paper
• Planning for Temporally Extended Goals as Propositional Satisfiability

  2007cited by this paper
• Declarative Programming for Modular Robots

  2007cited by this paper
• Compact Representation of Sets of Binary Constraints

  2006cited by this paper
• Scalable shape sculpting via hole motion: motion planning in lattice-constrained modular robots

  2006cited by this paper
• Planning as satisfiability: parallel plans and algorithms for plan search

  2006cited by this paper
• A Stochastic Non-CNF SAT Solver

  2006cited by this paper
• PRICAI 2006: Trends in Artificial Intelligence, 9th Pacific Rim International Conference on Artificial Intelligence, Guilin, China, August 7-11, 2006, Proceedings

  2006cited by this paper
• Solving Non-Boolean Satisfiability Problems with Stochastic Local Search: A Comparison of Encodings

  2005cited by this paper
• Generation of Hard Non-Clausal Random Satisfiability Problems

  2005cited by this paper
• Distributed self-reconfiguration control of modular robot M-TRAN

  2005cited by this paper
• Algorithms for fast concurrent reconfiguration of hexagonal metamorphic robots

  2005cited by this paper
• A framework for self -reconfiguration planning for unit -modular robots

  2005cited by this paper
• Parallel Encodings of Classical Planning as Satisfiability

  2004cited by this paper
• Metamodule Control for the ATRON Self-Reconfigurable Robotic System

  2004cited by this paper
• Evaluation Strategies for Planning as Satisfiability

  2004cited by this paper
• Solving Non-clausal Formulas with DPLL search

  2004cited by this paper
• Local Search on SAT-encoded Colouring Problems

  2003cited by this paper
• Symmetry Reduction for SAT Representations of Transition Systems

  2003cited by this paper
• Theory and Applications of Satisfiability Testing

  2003cited by this paper
• Distributed replication algorithms for self-reconfiguring modular robots

  2002cited by this paper
• Arc Consistency in SAT

  2002cited by this paper
• Telecubes: mechanical design of a module for self-reconfigurable robotics

  2002cited by this paper
• M-TRAN: self-reconfigurable modular robotic system

  2002cited by this paper
• On the general reconfiguration problem for expanding cube style modular robots

  2002cited by this paper
• A Hybrid Genetic Algorithm for the Satisfiability Problem

  2002cited by this paper
• Hormone-inspired adaptive communication and distributed control for CONRO self-reconfigurable robots

  2002cited by this paper
• Crystalline Robots: Self-Reconfiguration with Compressible Unit Modules

  2001cited by this paper
• A multi-layered planner for self-reconfiguration of a uniform group of I-Cube modules

  2001cited by this paper
• Guest Editorial: Self-Reconfigurable Robots

  2001cited by this paper
• Solving Non-Boolean Satisfiability Problems with Stochastic Local Search

  2001cited by this paper
• Finding perceived pattern structures using genetic programming

  2001cited by this paper
• A logical model of HCP

  2001cited by this paper
• Finding simplest pattern structures using genetic programming

  2001cited by this paper
• Partial Implicit Unfolding in the Davis-Putnam Procedure for Quantified Boolean Formulae

  2001cited by this paper
• SAT v CSP

  2000cited by this paper
• Applying the Davis-Putnam Procedure to Non-clausal Formulas

  1999cited by this paper
• Numeric State Variables in Constraint-Based Planning

  1999cited by this paper
• SAT-Encodings, Search Space Structure, and Local Search Performance

  1999cited by this paper
• Unifying SAT-based and Graph-based Planning

  1999cited by this paper
• Self-reconfiguration planning for a class of modular robots

  1999cited by this paper
• Locomotion versatility through self-reconfiguration

  1999cited by this paper
• Self-organizing collective robots with morphogenesis in a vertical plane

  1998cited by this paper
• A Planning Algorithm not based on Directional Search

  1998cited by this paper
• Exploiting Variable Dependency in Local Search

  1997cited by this paper
• Useful metrics for modular robot motion planning

  1997cited by this paper
• Parametrizing Above Guaranteed Values: MaxSat and MaxCut

  1997cited by this paper
• Automatic SAT-Compilation of Planning Problems

  1997cited by this paper
• Genetic and hybrid algorithms for graph coloring

  1996cited by this paper
• Design And Implementation Of Metamorphic Robots

  1996cited by this paper
• Pushing the Envelope: Planning, Propositional Logic and Stochastic Search

  1996cited by this paper
• Algorithms for the satisfiability (SAT) problem: A survey

  1996cited by this paper
• Encoding Plans in Propositional Logic

  1996cited by this paper
• Davis and Putnam were Already Checking Forward

  1996cited by this paper
• Principles and Practice of Constraint Programming

  1995cited by this paper
• Local and temporal predicates in distributed systems

  1995cited by this paper
• Proceedings of the 6th International Conference on Genetic Algorithms

  1995cited by this paper
• Locomotion With A Unit-Modular Reconfigurable Robot

  1995cited by this paper
• Self-Organizing Machine

  1995cited by this paper
• A New Population-Based Method for Satisfiability Problems

  1994cited by this paper
• Contradicting Conventional Wisdom in Constraint Satisfaction

  1994cited by this paper
• Noise Strategies for Improving Local Search

  1994cited by this paper
• Applying GSAT to Non-Clausal Formulas (Research Note)

  1994cited by this paper
• Self-assembling machine

  1994cited by this paper
• SAT-Varible Complexity of Hard Combinatorial Problems

  1994cited by this paper
• Kinematics of a metamorphic robotic system

  1994cited by this paper
• New locomotion gaits

  1994cited by this paper
• Maximum cuts and largest bipartite subgraphs

  1993cited by this paper
• A linear programming and rounding approach to max 2-sat

  1993cited by this paper
• Embedding complex decision procedures inside an interactive theorem prover

  1993cited by this paper
• Stationary waves in cyclic swarms

  1992cited by this paper
• Planning as Satisfiability

  1992cited by this paper
• Self-organization of sensors for swarm intelligence

  1992cited by this paper
• Conceptual Design of a Modular Robot

  1992cited by this paper
• Self-organizing sensors by deterministic annealing

  1991cited by this paper
• Theoretical problems for the realization of distributed robotic systems

  1991cited by this paper
• Cellular robotic system (CEBOT) as one of the realization of self-organizing intelligent universal manipulator

  1990cited by this paper
• On the Parallel Complexity of Discrete Relaxation in Constraint Satisfaction Networks

  1990cited by this paper
• A generalized kinematic modeling method for modular robots

  1989cited by this paper
• Using Genetic Algorithms to Solve NP-Complete Problems

  1989cited by this paper
• The concept of cellular robotic system

  1988cited by this paper
• Dynamically reconfigurable robotic system

  1988cited by this paper
• A Dynamically Reconfigurable Robotic System (Concept Of A System And Optimal Configurations)

  1987cited by this paper

• Development of a new path-planning algorithm for lattice based self-reconfigurable modular robots with pivoting cube shaped modules

  2025cites this paper
• Machine learning for modular robots self-reconfiguration problem

  2025cites this paper
• Tentacle-Based Shape Shifting of Metamorphic Robots Using Fast Inverse Kinematics

  2023cites this paper
• Self-reconfiguration of PARTS: A parallel reconfiguration algorithm based on surface flow

  2023cites this paper
• Auto-Optimizing Connection Planning Method for Chain-Type Modular Self-Reconfiguration Robots

  2023cites this paper
• Reconfiguring Metamorphic Robots via SMT: Is It a Viable Way?

  2021cites this paper
• Engineering efficient and massively parallel 3D self-reconfiguration using sandboxing, scaffolding and coating

  2021cites this paper
• Self-reconfiguration of shape-shifting modular robots with triangular structure

  2021cites this paper
• NP-completeness of optimal planning problem for modular robots

  2019cites this paper
• A survey of autonomous self-reconfiguration methods for robot-based programmable matter

  2019cites this paper
• Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding Structure

  2019cites this paper
• Survey of Modular Robots and Developed Embedded Devices for Constructive and Computing Components

  2017cites this paper
• оБзоР ПРИМЕНЕНИЯ ФоРМАЛьНЫХ МЕТоДоВ В РоБоТоТЕХНИКЕ

  2016cites this paper
• Survey on research and development of reconfigurable modular robots

  2016cites this paper
• A second chance for the flexible specialisation with robotics? Ageing society in Korea as a case

  2015cites this paper
• Modular Reconfigurable Robotic Systems: Lattice Automata

  2015cites this paper
• The multi-robot forest coverage for weighted terrain

  2015cites this paper
• Modular robotic systems: Methods and algorithms for abstraction, planning, control, and synchronization

  2015cites this paper
• On Optimal Planning for DNA Nanomechanical Robots

  2014cites this paper
• Avoidance of Forbidden DNA Nanorobots Configurations in Patterned Immobilization of other Materials

  2014cites this paper
• A Method of Recognition of Human Hand and Body Gestures for Task-Level Learning from Demonstration

  2014cites this paper
• The Problem of Selection of Fingerprints for Topological Localization

  2013cites this paper
• The Problem of Selection of a Set of Partially Distinguishable Guards

  2013cites this paper
• Visual landmarks systems for humanoid robots

  2013cites this paper
• Visual Landmark Selection for Mobile Robot Navigation

  2013cites this paper
• Computational Experiments for the Problem of Hamiltonian Path with Fixed Number of Color Repetitions

  2013cites this paper
• Longest Common Parameterized Subsequences with Fixed Common Substring

  2013cites this paper
• The String Barcoding Problem

  2013cites this paper
• The Identity Checking Problem for Semigroups

  2013cites this paper
• The Force Law Design of Artificial Physics Optimization for Starting Population Selection for GSAT

  2013cites this paper
• On Hamilton Paths in Grid Graphs

  2013cites this paper
• Computational Experiments for the Problem of Footstep Planning for Humanoid Robots

  2013cites this paper
• On the Approximate Period Problem

  2013cites this paper
• A Genetic Algorithm with Expansion and Exploration Operators for the Maximum Satisfiability Problem

  2013cites this paper
• Coevolving Solutions of the 3-Satisfiability Problem

  2013cites this paper
• On Multiple Occurrences Shortest Common Superstring Problem

  2013cites this paper
• A System of Intelligent Algorithms for a Module of Onboard Equipment of Mobile Vehicles

  2013cites this paper
• The Farthest Substring Problem

  2013cites this paper
• Computational Experiments for the Problem of Sensor-Mission Assignment in Wireless Sensor Networks

  2013cites this paper
• Graph-Theoretic Models for the Module of Safe Planning for Control Systems of Mobile Robots

  2013cites this paper
• The Problem of Sensor-Mission Assignment in Wireless Sensor Networks

  2013cites this paper
• On Starting Population Selection for GSAT

  2013cites this paper
• Self-Learning of Robots and the Model of Hamiltonian Path with Fixed Number of Color Repetitions for Systems of Scenarios Creation

  2013cites this paper
• The Swap Common Superstring Problem

  2013cites this paper
• Building the Panoramic Image for Mobile Robot Localization

  2013cites this paper
• Anticipation in Simple Robot Navigation and Finding Regularities

  2012cites this paper
• Computational Experiments for the Problem of Selection of a Minimal Set of Visual Landmarks

  2012cites this paper
• Footstep Planning for Humanoid Robots

  2012cites this paper
• SAT Solvers for the Problem of Sensor Placement

  2012cites this paper
• The Hamiltonian Strictly Alternating Cycle Problem

  2012cites this paper
• Clustering algorithm in mobile ad hoc networks

  2012cites this paper
• The longest common parameterized subsequence problem

  2012cites this paper
• The Distinguishing String Selection Problem

  2012cites this paper
• On the Longest Common Subsequence Problem

  2012cites this paper
• The Hamiltonian Alternating Path Problem

  2012cites this paper
• Element Duplication Centre Problem and Railroad Tracks Recognition

  2012cites this paper
• The Problem of Finding Two Edge-Disjoint Hamiltonian Cycles

  2012cites this paper
• The Binary Paint Shop Problem

  2012cites this paper
• Partially Distinguishable Guards

  2012cites this paper
• The c-Fragment Longest Arc-Preserving Common Subsequence Problem

  2012cites this paper
• The Problem of Sensor Placement

  2012cites this paper
• The Farthest String Problem

  2012cites this paper
• Approximate periods of strings for absolute distances

  2012cites this paper
• Monochromatic s-t Paths in Edge-Colored Graphs

  2012cites this paper
• On the Optimal Reconfiguration Planning for Modular Self-Reconfigurable DNA Nanomechanical Robots

  2012cites this paper
• Robot self-awareness: usage of co-training for distance functions for sequences of images

  2012cites this paper
• Multi-agent Path Planning

  2012cites this paper
• Hamiltonian Alternating Cycles with Fixed Number of Color Appearances

  2012cites this paper
• Independent Systems of Semigroup Relations and Descriptions of Robotic Systems

  2012cites this paper
• On the Constrained Longest Common Subsequence Problem

  2010cites this paper