Abstract-This paper presenterar en grundlig analys av den computational komplexiteten av optimal omkonfigurering planering problem för kedjetyp modulära robotar, dvs.. Hitta det minsta antalet omkonfigureringssteg för att omvandla från den ursprungliga konfigurationen till målkonfigurationen. Den fastställer ett formellt bevis på att detta problem är NP-komplett, även om konfigurationerna är acykliska. Detta resultat ger en övertygande anledning till att en polynomalgoritm för optimal omkonfigureringsplan sannolikt inte finns. För att underlätta framtida utvärdering av omkonfigureringsalgoritmer ger pappret också de nedre och övre gränserna för det minsta antalet omkonfigureringssteg för varje givet omkonfigureringsproblem.
Optimal omkonfigurering för kedjebaserade robotar har nyligen visat sig vara NP-komplett REF.
On the complexity of optimal reconfiguration planning for modular reconfigurable robots
{'venue': '2010 IEEE International Conference on Robotics and Automation', 'journal': '2010 IEEE International Conference on Robotics and Automation', 'mag_field_of_study': ['Computer Science', 'Mathematics']}