{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:03:38Z","timestamp":1740179018164,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,4,17]],"date-time":"2023-04-17T00:00:00Z","timestamp":1681689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,17]],"date-time":"2023-04-17T00:00:00Z","timestamp":1681689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC 2120\/1 - 390831618"],"award-info":[{"award-number":["EXC 2120\/1 - 390831618"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009534","name":"Universit\u00e4t Stuttgart","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009534","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constr Robot"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The technology of functionally graded concrete (FGC) is a new methodology in the field of concrete construction, striving for mass savings by adjusting the elements interior design. A promising approach herein is meso-gradation, where concrete hollow spheres are placed inside the formwork before casting the element; this allows up to 50% mass savings without a loss in load-bearing capacity, whilst also ensuring recyclability compared to e.g. bubble decks. In order to prevent damage\/displacement of the spheres during automated fabrication, the extruded concrete flow must avoid the spheres, whilst neatly covering the elements area in order to prevent cavities. Both requirements formulate a complex path planning problem that must be solved in order to achieve automated fabrication. In this paper, we propose a method for solving this problem, which is based on theoretical findings on Hamiltonian triangulations. Our approach is based on the idea that the elements area is triangulated, such that all sphere centers are corners of triangles. For each triangle, a smooth path can be planned straightforwardly on a consideration of the geometry, such that the global path is made of a sequence of local ones. This necessitates finding a triangulation that is hamiltonian, i.e. a sequence where all triangles are visited exactly once. To this end, we first present a new class of triangulations and proof their hamiltonicity, followed by an algorithm that generates such triangulations on certain FGC element geometries. This is followed by the local path planning problem, whose special structure with start\/end tangential and curvature constraints facilitates the use of a polar coordinate approach.<\/jats:p>","DOI":"10.1007\/s41693-023-00096-5","type":"journal-article","created":{"date-parts":[[2023,4,17]],"date-time":"2023-04-17T02:01:55Z","timestamp":1681696915000},"page":"125-139","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Path planning for graded concrete element fabrication"],"prefix":"10.1007","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2637-6527","authenticated-orcid":false,"given":"Boris","family":"Blagojevic","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6910-2473","authenticated-orcid":false,"given":"Oliver","family":"Sawodny","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,17]]},"reference":[{"key":"96_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41693-022-00066-3","volume":"6","author":"T Adams","year":"2022","unstructured":"Adams T, Heuer C, Brell-Cokcan S (2022) Dynamic 3D print head for spatial strand extrusion of fiber-reinforced concrete: requirements, development and application. Construct Robot 6:1\u201313","journal-title":"Construct Robot"},{"issue":"6","key":"96_CR2","doi-asserted-by":"publisher","first-page":"2157","DOI":"10.1109\/TSMC.2018.2806840","volume":"50","author":"V An","year":"2020","unstructured":"An V, Qu Z, Crosby F, Roberts R, An V (2020) A triangulation-based coverage path planning. IEEE Trans Syst Man Cybern Syst 50(6):2157\u20132169","journal-title":"IEEE Trans Syst Man Cybern Syst"},{"key":"96_CR3","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/BF01782475","volume":"12","author":"E Arkin","year":"2005","unstructured":"Arkin E, Held M, Mitchell JBM, Skiena S (2005) Hamiltonian triangulations for fast rendering. Vis Comput 12:429\u2013444","journal-title":"Vis Comput"},{"key":"96_CR4","first-page":"07","volume":"96","author":"B Bagheri","year":"2020","unstructured":"Bagheri B, Feder T, Fleischner H, Subi C (2020) Hamiltonian cycles in planar cubic graphs with facial 2-factors, and a new partial solution of Barnette\u2019s conjecture. J Graph Theory 96:07","journal-title":"J Graph Theory"},{"key":"96_CR5","doi-asserted-by":"crossref","unstructured":"Blagojevic B, Sch\u00f6nemann B, Nigl D, Blandini L, Sawodny O (2021) Trajectory planning for concrete element fabrication with optimal control. In: IECON 2021\u201447th annual conference of the IEEE industrial electronics society, pp 1\u20136","DOI":"10.1109\/IECON48115.2021.9589695"},{"key":"96_CR6","unstructured":"Bubble Deck North America LLC (2018) Bubble deck technology description"},{"key":"96_CR7","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.comgeo.2017.06.001","volume":"68","author":"J Cardinal","year":"2018","unstructured":"Cardinal J, Hoffmann M, Kusters V, T\u00f3th CD, Wettstein M (2018) Arc diagrams, flip distances, and Hamiltonian triangulations. Comput Geom 68:206\u2013225","journal-title":"Comput Geom"},{"issue":"94","key":"96_CR8","first-page":"642","volume":"7","author":"KP Cheng","year":"2019","unstructured":"Cheng KP, Mohan RE, Nhan NHK, Le AV (2019) Graph theory-based approach to accomplish complete coverage path planning tasks for reconfigurable robots. IEEE Access 7(94):642\u2013657","journal-title":"IEEE Access"},{"key":"96_CR9","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01553881","volume":"4","author":"P Chew","year":"1989","unstructured":"Chew P (1989) Constrained Delaunay triangulations. Algorithmica 4:97\u2013108","journal-title":"Algorithmica"},{"issue":"3","key":"96_CR10","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0166-218X(93)90111-Z","volume":"43","author":"RJ Cimikowski","year":"1993","unstructured":"Cimikowski RJ (1993) On certain Hamiltonian inner triangulations. Discrete Appl Math 43(3):185\u2013195","journal-title":"Discrete Appl Math"},{"issue":"18","key":"96_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3390\/su141811269","volume":"14","author":"D Frost","year":"2022","unstructured":"Frost D, Gericke O, Di Bari R, Balang\u00e9 L, Zhang L, Blagojevic B, Nigl D, Haag P, Blandini L, J\u00fcnger HC, Kropp C, Leistner P, Sawodny O, Schwieger V, Sobek W (2022) Holistic quality model and assessment-supporting decision-making towards sustainable construction using the design and production of graded concrete components as an example. Sustainability 14(18):1","journal-title":"Sustainability"},{"key":"96_CR12","doi-asserted-by":"crossref","unstructured":"Garey MR, Johnson DS, Tarjan RE (1976a) The planar Hamiltonian circuit problem is np-complete. SIAM J Comput 5(4):704\u2013714","DOI":"10.1137\/0205049"},{"key":"96_CR13","doi-asserted-by":"crossref","unstructured":"Garey M, Johnson D, Stockmeyer L (1976b) Some simplified np-complete graph problems. Theoret Comput Sci 1(3):237\u2013267","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"96_CR14","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1111\/j.1467-8659.2004.00768.x","volume":"23","author":"M Gopi","year":"2004","unstructured":"Gopi M, Eppstein D (2004) Single-strip triangulation of manifolds with arbitrary topology. Comput Graph F 23:371\u2013378","journal-title":"Comput Graph F"},{"key":"96_CR15","first-page":"1","volume":"2022","author":"D Hahlbrock","year":"2022","unstructured":"Hahlbrock D, Braun M, Heidel R, Lemmen P, Boumann R, Bruckmann T, Schramm D, Helm V, Willmann J (2022) Cable robotic 3D-printing: additive manufacturing on the construction site. Construct Robot 2022:1\u201314","journal-title":"Construct Robot"},{"issue":"14","key":"96_CR16","doi-asserted-by":"publisher","first-page":"1833","DOI":"10.1016\/j.dam.2007.03.018","volume":"155","author":"G Helden","year":"2007","unstructured":"Helden G (2007) Each maximal planar graph with exactly two separating triangles is Hamiltonian. Discret Appl Math 155(14):1833\u20131836","journal-title":"Discret Appl Math"},{"key":"96_CR17","doi-asserted-by":"publisher","first-page":"105388","DOI":"10.1016\/j.conengprac.2022.105388","volume":"131","author":"APR Lauer","year":"2023","unstructured":"Lauer APR, Lerke O, Blagojevic B, Schwieger V, Sawodny O (2023) Tool center point control of a large-scale manipulator using absolute position feedback. Control Eng Pract 131:105388","journal-title":"Control Eng Pract"},{"key":"96_CR18","unstructured":"Nigl D, Gericke O, Blandini L, Sobek W (2022) Numerical investigations on the biaxial load-bearing behaviour of graded concrete slabs. In: Proceedings of the fib congress, pp 110\u2013115 (in press)"},{"key":"96_CR19","unstructured":"Schmeer D, Sobek W (2017) Weight-optimized and mono-material concrete components by the integration of mineralized hollow spheres. In: Proceedings of IASS annual symposium"},{"issue":"2","key":"96_CR20","doi-asserted-by":"publisher","first-page":"378","DOI":"10.2307\/1968197","volume":"32","author":"H Whitney","year":"1931","unstructured":"Whitney H (1931) A theorem on graphs. Ann Math 32(2):378\u2013390","journal-title":"Ann Math"},{"issue":"12","key":"96_CR21","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1002\/best.201600056","volume":"111","author":"M W\u00f6rner","year":"2016","unstructured":"W\u00f6rner M, Schmeer D, Schuler B, Pfinder J, Garrecht H, Sawodny O, Sobek W (2016) Gradientenbetontechnologie. Beton- und Stahlbetonbau 111(12):794\u2013805","journal-title":"Beton- und Stahlbetonbau"}],"container-title":["Construction Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41693-023-00096-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41693-023-00096-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41693-023-00096-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T15:24:38Z","timestamp":1690471478000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41693-023-00096-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,17]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["96"],"URL":"https:\/\/doi.org\/10.1007\/s41693-023-00096-5","relation":{},"ISSN":["2509-811X","2509-8780"],"issn-type":[{"type":"print","value":"2509-811X"},{"type":"electronic","value":"2509-8780"}],"subject":[],"published":{"date-parts":[[2023,4,17]]},"assertion":[{"value":"12 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that there are no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}