Golf ball picker robot: path generation in unstructured environments towards multiple targets

Abstract

The new TWIN-RRT* algorithm solves a motion planning problem in which an agent has multiple possible targets where none of them is compulsory, and retrieves feasible, ―low cost‖, asymptotically optimal and probabilistically complete paths. The TWIN-RRT* algorithm solves path planning problems for both holonomic and non-holonomic robots with or without kinodynamic constraints in a 2D environment, but it was designed to work as well with higher DOF agents and different applications. The new algorithm provides a practical implementation of feasible and fast planning especially where a closed loop is required. Initial and final configurations are allowed to be exactly the same. The TWIN-RRT* algorithm computes an efficient path for one sole agent towards multiple targets where none of them is mandatory. It inherits the low computational cost, probabilistic completeness and asymptotical optimality from RRT*. It uses efficiency as cost function, which can be adapted depending on the application. The TWIN-RRT* complies both with kinodynamic constraints and different cost functions. It was developed to solve a real problem where a robot has to collect golf balls in a driving range, where thousands of balls accumulate every day. This thesis is part of a bigger project, Golfminho, to develop an autonomous robot capable of efficiently collecting balls in a golf practice field.

O novo algoritmo TWIN-RRT* resolve problemas de planeamento de trajetórias em que um agente tem múltiplos alvos, onde nenhum deles é obrigatório, e produz um plano exequível, de "baixo custo" computacional, assintoticamente ótimo e probabilisticamente completo. O TWINRRT* resolve problemas de planeamento de trajetórias tanto para robôs holonómicos como não holonómicos com ou sem restrições cinemáticas e/ou dinâmicas num ambiente 2D, mas foi projetado para funcionar também com agentes com maiores graus de liberdade e em diferentes aplicações. O novo algoritmo fornece uma implementação prática de um planeamento viável e rápido, especialmente quando é necessário produzir uma trajetória fechada. As configurações iniciais e finais podem ser exatamente iguais. O algoritmo TWIN-RRT* calcula um caminho eficiente para um agente único em direção a múltiplos alvos, onde nenhum deles é obrigatório. Herda o baixo custo computacional, integralidade probabilística e otimização assintótica do RRT*. Usa a eficiência como função de custo, que pode ser adaptada em função das diferentes aplicações. Para além de diferentes funções de custo, o TWIN-RRT* também mostra conformidade com restrições cinemáticas. Foi desenvolvido para resolver um problema real em que um robô tem que recolher bolas de golfe num Driving Range, onde se acumulam milhares de bolas de golfe por dia. Esta tese é parte integrante do projeto Golfminho, para o desenvolvimento de um robô autónomo capaz de recolher eficientemente bolas num campo de práticas de golfe.