Path planning for a telescopic boom lift robot

Abstract

Denne oppgaven presenterer fem ulike algoritmer for en teleskopisk bom lift. Liften vasker en to dimensjonal overflate med en mindre robot arm montert på liften. Robotarmen har et arbeidsområde på en sirkel. Hovedproblemet i denne oppgaven er å finne korteste vei mellom disse sirklene. Sirklene må bli besøkt i en bestemt rekkefølge, fra bunnen til toppen. Vurderingskriteriene for algoritmene er beregningstid og distanse på løsningen. Algoritmene som er testet er genetisk algoritme(GA), nærmeste nabo(NN) med 2-opt og løse det som et optimaliseringsproblem(ILP). Dei to siste algoritmene er forbedring av NN og ILP, for å fungere bedre med problemet i denne oppgaven. Den forbedrede ILP reduserer antall variabler. Algoritmene er testet på to forskjellige problemer. Dei best fungerende algoritmene er forbedrede versjoner av NN og ILP.

This thesis present five different algorithms for path planning for a telescopic boom lift robot. The boom lift is cleaning a 2-dimensional surface with a smaller robot arm mounted to the lift basket. The smaller robot arm has a working area of circle in 2D, called a washing circle. The main task for this thesis is to find the shortest possible path between these washing circles. The circles has to be visited in a specific order, from top to bottom. The evaluation metrics for the path are computation time and euclidean length of the path. The algorithms tested are genetic algorithm(GA), nearest neighbour(NN) with 2-opt, solving TSP as ILP. The two last algorithms are modifications of NN and TSP ILP to suit the specified problem in this thesis better. The improved version of TSP ILP has a pre-procession of data, to reduce variables in the optimization problem. The algorithms are tested on two different example jobs. The best performing algorithms on these tests are the modified NN and pre-processed optimization.