Exploring Grammar-Guided Design and Evolution of Polyominoes with Modular Soft Robots

Exploring Grammar-Guided Design and Evolution of Polyominoes with Modular Soft Robots | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Exploring Grammar-Guided Design and Evolution of Polyominoes with Modular Soft Robots Jessica Mégane, Eric Medvet, Nuno Lourenço, Penousal Machado This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-6982435/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 24 Mar, 2026 Read the published version in Genetic Programming and Evolvable Machines → Version 1 posted 4 You are reading this latest preprint version Abstract Languages for describing two-dimensional (2-D) structures have become powerful tools across multiple fields, including pattern recognition, image processing, and the modeling of physical and chemical phenomena. One of such structures is labeled polyominoes, i.e., geometric shapes formed by connected unit squares arranged on a 2-D grid. In previous work, we introduced: (a) a novel grammar-based approach for defining sets of labeled polyominoes that satisfy predefined requirements, and (b) an algorithm to develop labeled polyominoes following the rules of the proposed grammar. We demonstrated that these two components enable optimization within the space of labeled polyominoes, similarly to how grammatical evolution and its extensions operate in string-based search spaces. In this work, we extend our previous approach to a new domain: the evolution of modular soft robots, namely, voxel-based soft robots (VSRs). We evolve VSRs for the task of energy-efficient locomotion, while constraining their physical structure to adhere to a given grammar. We show that the evolved robots successfully perform their assigned tasks and do have the required structure. These results highlight the potential of integrating domain knowledge through grammars to guide the evolutionary design of complex structure as modular soft robots. polyomino grammar representation 2-D patterns voxel-based soft robots Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 24 Mar, 2026 Read the published version in Genetic Programming and Evolvable Machines → Version 1 posted Editorial decision: Revision requested 02 Jul, 2025 Editor assigned by journal 30 Jun, 2025 Submission checks completed at journal 26 Jun, 2025 First submitted to journal 26 Jun, 2025 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-6982435","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":479372423,"identity":"8a876594-e954-475d-a6f5-8339258fe93d","order_by":0,"name":"Jessica Mégane","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA0ElEQVRIiWNgGAWjYBACxgYgkQDE/EDyAGlaJBtgWtiItc7gQAKURUgLc3v74w8PauzkjY8nHzzA2GbHYC7fQMBhPWfMJBKOJRtuO/MsAaglmcGyjYAtjDNy2BgSG5gTzG7kGAC1HGAwOEZIy/znjz8kNtQnGM/I/0CklhkMBhKJDYcTDCRyGIjU0pMD8stxwxlnngED7Vwyj2VbAn4thu3HH3/8UVMtz9+e/PjDhzI7OXPmAwS0NCDzgObzGBBwF4M8hghBLaNgFIyCUTDiAADTtEVce0aGRQAAAABJRU5ErkJggg==","orcid":"","institution":"University of Coimbra, CISUC/LASI – Centre for Informatics and Systems of the University of Coimbra","correspondingAuthor":true,"prefix":"","firstName":"Jessica","middleName":"","lastName":"Mégane","suffix":""},{"id":479372424,"identity":"49599598-5bde-46f4-8f42-994089111548","order_by":1,"name":"Eric Medvet","email":"","orcid":"","institution":"University of Trieste","correspondingAuthor":false,"prefix":"","firstName":"Eric","middleName":"","lastName":"Medvet","suffix":""},{"id":479372426,"identity":"f9caf8f6-603f-4618-a1ed-65224fd03755","order_by":2,"name":"Nuno Lourenço","email":"","orcid":"","institution":"University of Coimbra, CISUC/LASI – Centre for Informatics and Systems of the University of Coimbra","correspondingAuthor":false,"prefix":"","firstName":"Nuno","middleName":"","lastName":"Lourenço","suffix":""},{"id":479372428,"identity":"7136f5fb-3c05-450e-b171-ef8fe7d50802","order_by":3,"name":"Penousal Machado","email":"","orcid":"","institution":"University of Coimbra, CISUC/LASI – Centre for Informatics and Systems of the University of Coimbra","correspondingAuthor":false,"prefix":"","firstName":"Penousal","middleName":"","lastName":"Machado","suffix":""}],"badges":[],"createdAt":"2025-06-26 10:23:36","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-6982435/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-6982435/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s10710-026-09534-z","type":"published","date":"2026-03-24T16:08:36+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":105756038,"identity":"ea8b2991-a5a0-4b62-b622-073e919e4e72","added_by":"auto","created_at":"2026-03-30 16:34:33","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":661612,"visible":true,"origin":"","legend":"","description":"","filename":"2025GPEMGrammarBasedPolyominoesEvolution.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6982435/v1_covered_e3027f87-6803-4a84-bb71-4894b0e534e0.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Exploring Grammar-Guided Design and Evolution of Polyominoes with Modular Soft Robots","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"genetic-programming-and-evolvable-machines","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"genp","sideBox":"Learn more about [Genetic Programming and Evolvable Machines](http://link.springer.com/journal/10710)","snPcode":"10710","submissionUrl":"https://submission.nature.com/new-submission/10710/3","title":"Genetic Programming and Evolvable Machines","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"polyomino, grammar, representation, 2-D patterns, voxel-based soft robots","lastPublishedDoi":"10.21203/rs.3.rs-6982435/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-6982435/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Languages for describing two-dimensional (2-D) structures have become powerful tools across multiple fields, including pattern recognition, image processing, and the modeling of physical and chemical phenomena. One of such structures is labeled polyominoes, i.e., geometric shapes formed by connected unit squares arranged on a 2-D grid. In previous work, we introduced: (a) a novel grammar-based approach for defining sets of labeled polyominoes that satisfy predefined requirements, and (b) an algorithm to develop labeled polyominoes following the rules of the proposed grammar. We demonstrated that these two components enable optimization within the space of labeled polyominoes, similarly to how grammatical evolution and its extensions operate in string-based search spaces. In this work, we extend our previous approach to a new domain: the evolution of modular soft robots, namely, voxel-based soft robots (VSRs). We evolve VSRs for the task of energy-efficient locomotion, while constraining their physical structure to adhere to a given grammar. We show that the evolved robots successfully perform their assigned tasks and do have the required structure. These results highlight the potential of integrating domain knowledge through grammars to guide the evolutionary design of complex structure as modular soft robots.","manuscriptTitle":"Exploring Grammar-Guided Design and Evolution of Polyominoes with Modular Soft Robots","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-10-09 08:31:02","doi":"10.21203/rs.3.rs-6982435/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2025-07-02T04:41:18+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2025-06-30T15:22:22+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2025-06-27T03:48:23+00:00","index":"","fulltext":""},{"type":"submitted","content":"Genetic Programming and Evolvable Machines","date":"2025-06-26T10:15:46+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"genetic-programming-and-evolvable-machines","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"genp","sideBox":"Learn more about [Genetic Programming and Evolvable Machines](http://link.springer.com/journal/10710)","snPcode":"10710","submissionUrl":"https://submission.nature.com/new-submission/10710/3","title":"Genetic Programming and Evolvable Machines","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"20a72034-7349-46f1-85be-9a7ec45eb493","owner":[],"postedDate":"October 9th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2026-03-30T16:29:26+00:00","versionOfRecord":{"articleIdentity":"rs-6982435","link":"https://doi.org/10.1007/s10710-026-09534-z","journal":{"identity":"genetic-programming-and-evolvable-machines","isVorOnly":false,"title":"Genetic Programming and Evolvable Machines"},"publishedOn":"2026-03-24 16:08:36","publishedOnDateReadable":"March 24th, 2026"},"versionCreatedAt":"2025-10-09 08:31:02","video":"","vorDoi":"10.1007/s10710-026-09534-z","vorDoiUrl":"https://doi.org/10.1007/s10710-026-09534-z","workflowStages":[]},"version":"v1","identity":"rs-6982435","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-6982435","identity":"rs-6982435","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}