{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,12]],"date-time":"2026-08-12T13:32:29Z","timestamp":1786541549688,"version":"build-2736575974"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,5,25]],"date-time":"2026-05-25T00:00:00Z","timestamp":1779667200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,25]],"date-time":"2026-05-25T00:00:00Z","timestamp":1779667200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e9 Marie et Louis Pasteur"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper Res Int J"],"published-print":{"date-parts":[[2026,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Recent years have shown continuous progress in nanoscale assembly with the development of affordable large-scale manufacturing technologies. Modular robotics and, especially, the programmable matter is one of the emanations of this evolution, which consists of a set of identical modular robots capable of reconfiguring into any shape. However, the success of such a technology depends on the provided algorithmic solutions that allow shifting from the current configuration to the targeted shape. Major works concerning the modular robots self-reconfiguration problem (MRSR) are based on local and\/or distributed heuristics that do not guarantee the optimality of the reconfiguration proposals in terms of energy and convergence time. Furthermore, centralized approaches employ constraint relaxation to reduce the combinatorial complexity of the problem. Therefore, obtained solutions are not practically usable in the physical world. In this paper, we provide the first modeling of the modular-robots self-reconfiguration problem into Mixed-Integer Quadratic Programming Model (MIQP). The model includes at the best of our knowledge all the physical, synchronization, and operational constraints of the horizontal 6-lattice MRSR problem. Modeling the MRSR problem as a MIQP problem allows to use exact optimization solvers to pre-calculate the best reconfiguration plan or to prove the problem\u2019s unfeasibility. The obtained results show the relevance of the MIQP approach, especially for small and mid-size instances. Problems with 10 robots could be solved in a few seconds with sometimes the proof of optimality.<\/jats:p>","DOI":"10.1007\/s12351-026-01052-1","type":"journal-article","created":{"date-parts":[[2026,5,25]],"date-time":"2026-05-25T02:19:46Z","timestamp":1779675586000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Mixed integer quadratic programming for modular robots self reconfiguration problem"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8358-4029","authenticated-orcid":false,"given":"Hakim","family":"Mabed","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Herv\u00e9","family":"Manier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marie-Ange","family":"Manier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baptiste","family":"Buchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,25]]},"reference":[{"key":"1052_CR1","doi-asserted-by":"publisher","unstructured":"Auerbach J, Aydin D, Maesani A, Kornatowski P, Cieslewski T, Heitz G, Fernando P, Loshchilov I, Daler L, Floreano D (2014) Robogen: Robot generation through artificial evolution, pp. 136\u2013137. https:\/\/doi.org\/10.7551\/978-0-262-32621-6-ch022","DOI":"10.7551\/978-0-262-32621-6-ch022"},{"key":"1052_CR2","doi-asserted-by":"crossref","unstructured":"Badri-Spr\u00f6witz A, Asadpour M, Billard A, Dillenbourg P, Ijspeert AJ (2010) Roombots\u2013modular robots for adaptive furniture","DOI":"10.1109\/MCI.2010.937320"},{"key":"1052_CR3","doi-asserted-by":"publisher","unstructured":"Bassil J, Tannoury P, Piranda B, Makhoul A, Bourgeois J (2022) Fault- tolerance mechanism for self-reconfiguration of modular robots. In: 2022 international wireless communications and mobile computing (IWCMC), pp 360\u2013365. https:\/\/doi.org\/10.1109\/IWCMC55113.2022.9825002","DOI":"10.1109\/IWCMC55113.2022.9825002"},{"key":"1052_CR4","unstructured":"Bateau J, Clark A, McEachern K, Schuetze Walter J (2012) Increasing the efficiency of distributed goal-filling algorithms for self-reconfigurable hexagonal metamorphic robots. pp 509\u2013515"},{"key":"1052_CR5","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1109\/70.499830","volume":"12","author":"G Beni","year":"1996","unstructured":"Beni G, Liang P (1996) Pattern reconfiguration in swarms - convergence of a distributed asynchronous and bounded iterative algorithm. Robot Autom IEEE Trans 12:485\u2013490. https:\/\/doi.org\/10.1109\/70.499830","journal-title":"Robotics and Automation IEEE Transactions on"},{"key":"1052_CR6","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1109\/ICMAS.2000.858446","volume":"142","author":"H Bojinov","year":"2000","unstructured":"Bojinov H, Casal A, Hogg T (2000) Multiagent control of self-reconfigurable robots 142:143\u2013150. https:\/\/doi.org\/10.1109\/ICMAS.2000.858446","journal-title":"Multiagent control of self-reconfigurable robots"},{"key":"1052_CR7","doi-asserted-by":"publisher","unstructured":"Buchi B, Mabed H, Lassabe F, Gaber J, Abdou W (2021) Translation based self reconfiguration algorithm for 6-lattice modular robots. In: 2021 20th international symposium on parallel and distributed computing (ISPDC), pp 49\u201356. https:\/\/doi.org\/10.1109\/ISPDC52870.2021.9521628","DOI":"10.1109\/ISPDC52870.2021.9521628"},{"key":"1052_CR8","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1109\/ROBOT.2002.1013457","volume":"1","author":"Z Butler","year":"2002","unstructured":"Butler Z, Kotay K, Rus D, Tomita K (2002) Generic decentralized control for a class of self-reconfigurable robots 1:809\u20138161. https:\/\/doi.org\/10.1109\/ROBOT.2002.1013457","journal-title":"Generic decentralized control for a class of self-reconfigurable robots"},{"key":"1052_CR9","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1023\/A:1026552720914","volume":"10","author":"CJ Chiang","year":"2001","unstructured":"Chiang CJ, Chirikjian G (2001) Modular robot motion planning using similarity metrics. Auton Robots 10:91\u2013106. https:\/\/doi.org\/10.1023\/A:1026552720914","journal-title":"Auton Robots"},{"key":"1052_CR10","doi-asserted-by":"publisher","unstructured":"Chirikjian GS (1994) Kinematics of a metamorphic robotic system. In: Proceedings of the 1994 IEEE international conference on robotics and automation, pp 449\u20134551. https:\/\/doi.org\/10.1109\/ROBOT.1994.351256","DOI":"10.1109\/ROBOT.1994.351256"},{"key":"1052_CR11","doi-asserted-by":"crossref","unstructured":"Christensen DJ (2006) Evolution of shape-changing and self-repairing control for the atron self-reconfigurable robot. In: Proceedings 2006 IEEE international conference on robotics and automation, ICRA 2006, pp 2539\u20132545","DOI":"10.1109\/ROBOT.2006.1642084"},{"key":"1052_CR12","doi-asserted-by":"crossref","unstructured":"Deng Y, Hua Y, Napp N, Petersen K (2019) A compiler for scalable construction by the termes robot collective. Robot Auton Syst 121","DOI":"10.1016\/j.robot.2019.07.010"},{"key":"1052_CR13","unstructured":"Femto-ST: 2D-Catoms"},{"key":"1052_CR14","doi-asserted-by":"crossref","unstructured":"Fukuda T, Kawauchi Y (1990) Cellular robotic system (cebot) as one of the realization of self-organizing intelligent universal manipulator. pp 662\u20136671","DOI":"10.1109\/ROBOT.1990.126059"},{"key":"1052_CR15","doi-asserted-by":"publisher","unstructured":"Gerbl M, Pieber M, Ulrich E, Gerstmayr J (2024) Parts\u2013a 2d self-reconfigurable programmable mechanical structure. Robotics 13(5) https:\/\/doi.org\/10.3390\/robotics13050077","DOI":"10.3390\/robotics13050077"},{"key":"1052_CR16","unstructured":"Goldstein JSC, Mowry TC (2004) Claytronics: An instance of programmable matter. Wild and Crazy Ideas Session of ASPLOS"},{"key":"1052_CR17","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1134\/S0361768812010033","volume":"38","author":"A Gorbenko","year":"2012","unstructured":"Gorbenko A, Popov V (2012) Programming for modular reconfigurable robots. Program Comput Softw 38:13\u201323. https:\/\/doi.org\/10.1134\/S0361768812010033","journal-title":"Program Comput Softw"},{"key":"1052_CR18","doi-asserted-by":"publisher","unstructured":"Gross R, Tuci E, Dorigo M, Bonani M, Mondada F (2006) Object transport by modular robots that self-assemble. In: Proceedings 2006 IEEE international conference on robotics and automation, 2006. ICRA 2006, pp 2558\u20132564 https:\/\/doi.org\/10.1109\/ROBOT.2006.1642087","DOI":"10.1109\/ROBOT.2006.1642087"},{"key":"1052_CR19","unstructured":"Gurobi Optimization (2024) LLC: Gurobi optimizer reference manual. https:\/\/www.gurobi.com"},{"key":"1052_CR20","doi-asserted-by":"publisher","unstructured":"Holdcroft K, Bolotnikova A, Belke C, Paik J (2022) Modular robot networking: a novel schema and its performance assessment. In: 2022 IEEE\/RSJ international conference on intelligent robots and systems (IROS), pp 12698\u201312705. https:\/\/doi.org\/10.1109\/IROS47612.2022.9981688","DOI":"10.1109\/IROS47612.2022.9981688"},{"key":"1052_CR21","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-319-22979-9_3","volume-title":"Biomimetic and Biohybrid Systems","author":"AD Horchler","year":"2015","unstructured":"Horchler AD, Kandhari A, Daltorio KA, Moses KC, Andersen KB, Bunnelle H, Kershaw J, Tavel WH, Bachmann RJ, Chiel HJ, Quinn RD (2015) Worm-like robotic locomotion with a compliant modular mesh. In: Wilson SP, Verschure PFMJ, Mura A, Prescott TJ (eds) Biomimetic and biohybrid systems. Springer, Cham, pp 26\u201337"},{"key":"1052_CR22","doi-asserted-by":"publisher","unstructured":"Hourany E, Stephan C, Makhoul A, Piranda B, Habib B, Bourgeois J (2021) Self-reconfiguration of modular robots using virtual forces. In: 2021 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), pp 6948\u20136953. https:\/\/doi.org\/10.1109\/IROS51168.2021.9635889","DOI":"10.1109\/IROS51168.2021.9635889"},{"key":"1052_CR23","doi-asserted-by":"publisher","unstructured":"Hou F, Shen Wm (2010) On the complexity of optimal reconfiguration planning for modular reconfigurable robots, pp 2791\u20132796. https:\/\/doi.org\/10.1109\/ROBOT.2010.5509642","DOI":"10.1109\/ROBOT.2010.5509642"},{"key":"1052_CR24","doi-asserted-by":"crossref","unstructured":"Hult R, Zanon M, Gros S, Falcone P (2018) An miqp-based heuristic for optimal coordination of vehicles at intersections. IN: 2018 IEEE conference on decision and control (CDC), pp 2783\u20132790","DOI":"10.1109\/CDC.2018.8618945"},{"key":"1052_CR25","doi-asserted-by":"publisher","first-page":"1337","DOI":"10.1007\/s10514-018-9738-1","volume":"42","author":"G Jing","year":"2018","unstructured":"Jing G, Tosun T, Yim M, Kress-Gazit H (2018) Accomplishing high-level tasks with modular robots. Auton Robot 42:1337\u20131354","journal-title":"Auton Robot"},{"key":"1052_CR26","doi-asserted-by":"publisher","unstructured":"Jorgensen MW, Ostergaard EH, Lund HH (2004) Modular atron Modules for a self-reconfigurable robot 2:2068\u201320732. https:\/\/doi.org\/10.1109\/IROS.2004.1389702","DOI":"10.1109\/IROS.2004.1389702"},{"key":"1052_CR27","doi-asserted-by":"crossref","unstructured":"Kamimura A, Yoshida E, Murata S, Kurokawa H, Tomita K, Kokaji S (2002) A self-reconfigurable modular robot (mtran)\u2013hardware and motion generation software","DOI":"10.1007\/978-4-431-65941-9_3"},{"key":"1052_CR28","unstructured":"Karagozler ME (2012) Design, fabrication and characterization of an autonomous, sub-millimeter scale modular robot. PhD thesis, Carnegie Mellon University"},{"key":"1052_CR29","doi-asserted-by":"publisher","unstructured":"KotayKD, Rus DL (2000) Algorithms for self-reconfiguring molecule motion planning. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems, IROS 2000, Takamatsu, Japan, October 31-November 5, 2184\u20132193. https:\/\/doi.org\/10.1109\/IROS.2000.895294","DOI":"10.1109\/IROS.2000.895294"},{"key":"1052_CR30","doi-asserted-by":"publisher","unstructured":"Lakhlef H, Mabed H, Bourgeois J (2013) Distributed and efficient algorithm for self-reconfiguration of MEMS microrobots. In: Shin SY, Maldonado JC (eds) Proceedings of the 28th Annual ACM symposium on applied computing, SAC\u201913, Coimbra, Portugal, March 18-22, 2013, pp 560\u2013566. ACM. https:\/\/doi.org\/10.1145\/2480362.2480469 . https:\/\/doi.org\/10.1145\/2480362.2480469","DOI":"10.1145\/2480362.2480469"},{"key":"1052_CR31","doi-asserted-by":"publisher","unstructured":"Larkworthy T, Ramamoorthy S (2010) An efficient algorithm for self-reconfiguration planning in a modular robot, pp 5139\u20135146. https:\/\/doi.org\/10.1109\/ROBOT.2010.5509482","DOI":"10.1109\/ROBOT.2010.5509482"},{"key":"1052_CR32","doi-asserted-by":"publisher","unstructured":"Lengiewicz J, Ho\u0142obut P (2019) Efficient collective shape shifting and locomotion of massively-modular robotic structures. Auton Robots 43:97\u2013122 https:\/\/doi.org\/10.1007\/s10514-018-9709-6","DOI":"10.1007\/s10514-018-9709-6"},{"issue":"6","key":"1052_CR33","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1109\/JIOT.2016.2552381","volume":"3","author":"H Mabed","year":"2016","unstructured":"Mabed H, Bourgeois J (2016) Scalable distributed protocol for modular micro-robots network reorganization. IEEE Internet Things J 3(6):1070\u20131083. https:\/\/doi.org\/10.1109\/JIOT.2016.2552381","journal-title":"IEEE Internet Things J"},{"key":"1052_CR34","doi-asserted-by":"crossref","unstructured":"Mabed H, Bourgeois J (2014) A shape-shifting distributed meta-algorithm for modular robots. In: 12th IEEE international symposium on parallel and distributed processing with applications (ISPA 2014), pp 58\u201367. IEEE, Milan, Italy","DOI":"10.1109\/ISPA.2014.17"},{"key":"1052_CR35","doi-asserted-by":"publisher","unstructured":"Mabed H, Bourgeois J (2014) Towards programmable material: Flexible distributed algorithm for modular robots shape-shifting. In: IEEE\/ASME International conference on advanced intelligent mechatronics, AIM 2014, Besancon, France, July 8-11, 2014, pp 408\u2013414. IEEE. https:\/\/doi.org\/10.1109\/AIM.2014.6878113 . https:\/\/doi.org\/10.1109\/AIM.2014.6878113","DOI":"10.1109\/AIM.2014.6878113"},{"key":"1052_CR36","unstructured":"Mabed H, Lakhlef H, Bourgeois J (2012) Fully distributed redeployment algorithm for multi-robot system. In: 2012 6th international conference on network games, control and optimization (NetGCooP), pp 139\u2013144"},{"key":"1052_CR37","doi-asserted-by":"publisher","unstructured":"Mathews N, Christensen A, O\u2019Grady R, Mondada F, Dorigo M (2017) Mergeable nervous systems for robots. Nat Commun 8 https:\/\/doi.org\/10.1038\/s41467-017-00109-2","DOI":"10.1038\/s41467-017-00109-2"},{"key":"1052_CR38","doi-asserted-by":"publisher","unstructured":"Mendoza-Garcia RF, Hiller J, Stoy K, Lipson H (2011) A vacuum-based bonding mechanism for modular robotics. Robot, IEEE Trans 27:876\u2013890 https:\/\/doi.org\/10.1109\/TRO.2011.2153010","DOI":"10.1109\/TRO.2011.2153010"},{"key":"1052_CR39","doi-asserted-by":"publisher","unstructured":"Murshiduzzaman Saleh CEng\u00a0MIMechE, T, Khan MR (2019) Modular robotic platform for autonomous machining. Int J Adv Manuf Technol 105:1\u201311 https:\/\/doi.org\/10.1007\/s00170-019-04427-1","DOI":"10.1007\/s00170-019-04427-1"},{"key":"1052_CR40","doi-asserted-by":"crossref","unstructured":"Naz A, Piranda B, Bourgeois J, Goldstein SC (2016) A distributed self-reconfiguration algorithm for cylindrical lattice-based modular robots. In: 2016 IEEE 15th international symposium on network computing and applications (NCA), pp 254\u2013263","DOI":"10.1109\/NCA.2016.7778628"},{"key":"1052_CR41","unstructured":"Piranda B, Bourgeois J (2020) Datom: a deformable modular robot for building self-reconfigurable programmable matter"},{"key":"1052_CR42","doi-asserted-by":"crossref","unstructured":"Piranda B, Laurent GJ, Bourgeois J, Cl\u00e9vy C, Mobes S, Fort-Piat NL (2013) A new concept of planar self-reconfigurable modular robot for conveying microparts","DOI":"10.1016\/j.mechatronics.2013.08.009"},{"key":"1052_CR43","doi-asserted-by":"crossref","unstructured":"Romanishin JW, Gilpin K, Rus D (2013) M-blocks: momentum-driven, magnetic modular robots. In: 2013 IEEE\/RSJ international conference on intelligent robots and systems, pp 4288\u20134295","DOI":"10.1109\/IROS.2013.6696971"},{"key":"1052_CR44","doi-asserted-by":"crossref","unstructured":"Rubenstein M, Ahler C, Nagpal R (2012) Kilobot: a low cost scalable robot system for collective behaviors. In: 2012 IEEE international conference on robotics and automation, pp 3293\u20133298","DOI":"10.1109\/ICRA.2012.6224638"},{"key":"1052_CR45","doi-asserted-by":"publisher","unstructured":"Unsal KPKC (2001) A multi-layered planner for self-reconfiguration of a uniform group of i-cube modules. In: IEEE\/RSJ International conference on intelligent robots and systems IROS 2001, pp 598\u2013605. https:\/\/doi.org\/10.1109\/IROS.2001.973421","DOI":"10.1109\/IROS.2001.973421"},{"key":"1052_CR46","doi-asserted-by":"crossref","unstructured":"Yim M, Duff DG, Roufas KD (2000) Polybot: a modular reconfigurable robot. In: Proceedings 2000 ICRA. Millennium Conference. IEEE international conference on robotics and automation. Symposia Proceedings (Cat. No.00CH37065), Vol 1, pp 514\u20135201","DOI":"10.1109\/ROBOT.2000.844106"},{"key":"1052_CR47","unstructured":"Zhu L (2018) A distributed modular self-reconfiguring robotic platform based on simplified electro-permanent magnets. (plate-forme robotique auto-reconfigurable modulaire distribu\u00e9e bas\u00e9e sur des aimants \u00e9lectro-permanents simplifi\u00e9s). PhD thesis, Paul Sabatier University, France. https:\/\/tel.archives-ouvertes.fr\/tel-01829962"}],"container-title":["Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-026-01052-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12351-026-01052-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-026-01052-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,12]],"date-time":"2026-08-12T12:44:29Z","timestamp":1786538669000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12351-026-01052-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,25]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9]]}},"alternative-id":["1052"],"URL":"https:\/\/doi.org\/10.1007\/s12351-026-01052-1","relation":{},"ISSN":["1109-2858","1866-1505"],"issn-type":[{"value":"1109-2858","type":"print"},{"value":"1866-1505","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,25]]},"assertion":[{"value":"10 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 March 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing financial interests.","order":1,"name":"Ethics","label":"Conflict of interest","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This study is not subject to ethic approval.","order":2,"name":"Ethics","label":"Ethical approval","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"64"}}