A* in automation of modelling and clash avoidance in construction design

Abstract

Sammendrag Kontekst Byggbransjen er i dag de en av bransjene som scorer dårligst på digitalisering sammenliknet med andre bransjer. Samtidig har mye skjedd på digitaliseringsfronten innen bygningsdesign. Byggbransjen er på tur ut av en æra med 2D tegninger til fordel for BIM og etter hvert parametrisk modellering. Med framveksten nye dataprogrammer som tilrettelegger for videre utvikling har det aldri vært så enkelt som nå å utvikle nye verktøy for digital design av bygninger. Derfor kan det være interessant å se om man i byggbransjen kan lære av de bransjene som har kommet lenger i digitaliseringen og låne teknikker derfra. Målsetting Målsetningen med denne oppgaven er å utforske hvorvidt enkle problemer innen konstruksjonsdesign kan reduseres til stifinnerproblemer og dermed benytte stifinneralgoritmer til å automatisk finner en vei. En slik algoritme vil kunne oppdaterer seg hver gang noe endres og dermed automatisk unngå kollisjon. Dette vil da kunne spare tid og penger, og vil gli naturlig inn med parametrisk modellering. Metode For å teste dette i praksis ble det laget en plugin til det visuelle programmeringsgrensesnittet Grasshopper som er en del av CAD programmet Rhinoceros 6. I denne pluginen inneholder skreddersydde grasshopperkomponenter. Disse komponentene gir brukeren mulighet til å inndele eksisterende geometri i et rutenett og deretter kjøre A* stifinneralgoritmen for å finne en vei mellom to valgte ruter. Brukeren har mulighet til å påvirke hvilke veier algoritmen velger ved å endre på ulike verdier i algoritmens kostfunksjon. Til slutt vises resultatet i form av et rør modellert langs ruta mellom de to punktene. Resultat I ulike tester vises det hvordan algoritmen oppfører seg med ulike inputverdier. Det vises hvordan brukeren kan påvirke algoritmen til å ha ulike egenskaper ved å endre på inputverdiene. Det diskuteres om algoritmen oppfører seg ønskelig, i hvilke tilfeller den ikke gjør det og det gjøres også en kjøretidstest. Konklusjon og videre arbeid. Konklusjonen er at algoritmen viser lovende resultater, men at mye arbeid gjenstår. Det er en rekke ting som må forbedres med nåværende algoritme for å få den til å fungere mer optimalt. Blant dette er å minske antall svinger algoritmen velger å gjøre samt redusere kjøretid. Det er også en rekke deler av algoritmen som kan være interessant å utforske videre som heuristikkfunksjonen, kostfunksjonen men også andre stifinneralgoritmer.

Summary Context Today one of the lowest scoring sectors in digitalization is the construction sector. Still much has changed the last decade in the digitalization in structural design. The construction industry is leaving the era of 2D drawings in favor of BIM and eventually parametric modeling. With new design software that facilitates programming, it has never been easier to develop new tools for digital design of buildings. Therefore, it can be interesting to explore whether the construction industry can learn from the industries that have come further in digitization and borrow techniques from there. Objective The aim of this thesis is to explore whether simple design problems can be reduced to a path finding problem and thus use a path finding algorithm to solve the problem. Such an algorithm will be able to update itself every time something changes and thus automatically avoid collision. This will then save time and money, and will integrate smoothly with parametric modeling. Method To test this in practice, a plugin was created for the Grasshopper visual programming interface which is part of the Rhinoceros 6 CAD program. This plugin contains custom grasshopper components. These components allow the user to divide the space around existing geometry into a grid and then run the A* path finding algorithm to find a path between two selected points. The user har the ability to influence which path the algorithm chooses by changing different values in the algorithms cost function. Finally, the result is shown in the form of a pipe modelled along the path between the two points. Result The algorithm was run on different cases and with different input values to test how the algorithm behaves. It is shown how the user can influence the algorithm to have different properties by changing the input values. The algorithm showed promising results in some cases, while in other it did not. A run time test was also done. Conclusion and further work. The algorithm shows promising results, but a lot of work remains. There are a number of things that need to be improved with the current algorithm to make it work more optimally. Among these is to reduce the number of turns the algorithm chooses to do as well as reduce run time. There are also several elements of the algorithm that may be interesting to explore further such as the heuristic function, the cost function but also other path finding algorithms.