May 5, 2023

#152 - Chat with Francisco Bruno Dias Ribeiro Da Silva

 (English version at the bottom)


Tive o prazer de bater um papo com Francisco Bruno Dias Ribeiro Da Silva, estudante do último ano de engenharia do Instituto Tecnológico Aeronáutico (ITA) e líder de desenvolvimento de software na ITAndroids. Conversamos sobre as suas experiências otimizando algoritmos para aplicações de robôs humanoides que jogam futebol de forma autônoma, além do seu interesse por competições de programação.

Francisco teve grande afinidade pela área de exatas desde o ensino fundamental, quando começou a participar de olimpíadas nacionais de matemática. Com o passar dos anos seus conhecimentos para resolução de problemas matemáticos complexos foram se aprimorando e ele decidiu que iria cursar engenharia no ITA, uma das mais prestigiosas universidades do país.

Após passar no difícil processo de admissão do ITA, Francisco decidiu se dedicar extensivamente a aprender engenharia de software. Além das aulas de programação e de projetos pessoais criando apps, Francisco também integrou o time de desenvolvimento de software da ITAndroids. A ITAndroids é uma equipe de alunos do ITA que criam robôs para jogar futebol de forma autônoma em competições tais como a Robocup. Ela também promove o avanço tecnológico na área por meio de pesquisas e publicações cientificas relevantes e já conquistou vários prêmios ao longo dos anos.


Uma das maiores contribuições do Francisco para o robô humanoide da sua equipe, foi a realização e otimização de um algoritmo de calibração do modelo cinemático das juntas do robô que influenciam na qualidade da visão computacional do mesmo. Este robô, de aproximadamente cinquenta centímetros de altura, possui uma câmera posicionada na sua cabeça, a qual capta vinte imagens por segundo. Um software embarcado, utiliza uma técnica de fusão sensorial por filtro de Kalman, com base nos dados provenientes da câmera e do sensor inercial de 9-eixos (3D acelerômetro, 3D giroscópio e 3D magnetômetro), para calcular a posição, velocidade e orientação do robô no campo de futebol. O software embarcado também realiza a detecção de objetos importantes no campo, tais como as traves, as linhas dos limites do campo, a bola, entre outros. No entanto, se as juntas do robô não forem perfeitamente calibradas, os pequenos erros, de décimos de graus, nas posições dos servos motores das juntas induzem grandes erros, podendo chegar a dezenas de centímetros, nesse processo crítico para o desempenho do robô.


O algoritmo desenvolvido por Francisco se divide em duas partes principais. A primeira parte consiste em posicionar o robô em um ponto específico em cima de um tapete customizado que possui cento e vinte marcos, do tipo ArUco, cujas posições são conhecidas. Dados são coletados girando o pescoço do robô aproximadamente cento e oitenta graus por vinte segundos.

Em seguida, para cada marco ArUco, as medidas de posição obtidas são filtradas, removendo os valores que se encontram fora do intervalo de mais ou menos dois desvios padrão. A segunda parte, consiste em calcular o melhor coeficiente de ajuste do ângulo dos servos motores presentes nas cinco juntas responsáveis por essa operação: três juntas no pescoço e duas juntas no torço. O algoritmo de otimização para determinar os cinco ângulos adequados é chamado Nelder-Mead. O objetivo é encontrar o coeficiente de correção para cada junta, ou seja determinar o modelo cinemático ideal, que convirja para o menor valor de erro entre a posição real e a medida. Por fim, com o resultado obtido pelo programa, é necessário aplicar as correções nos sistemas mecânicos. Esse processo é repetido várias vezes até alcançar um resultado satisfatório. O programa de calibração foi escrito na linguagem C++ e compilado no g++ com flags especificas, como "-Ofast -fext-numericliterals -fPIC", para um melhor tempo de execução e praticidade durante uma competição.


Outro projeto que Francisco se dedica é voltado para competições de programação, as quais podem ser presenciais ou remotas. A plataforma russa Code Forces, por exemplo, promove regularmente competições de programação, onde são avaliadas as respostas corretas, mas também o desempenho do programa por meio da sua memória e tempo de execução. Por esses motivos, os programas são principalmente escritos em C++, e ocasionalmente em outras linguagens como Python ou Java. Francisco comentou ser importante ler atentamente o enunciado e entender o objetivo da questão. Em seguida é recomendado esboçar os pontos principais da resolução utilizando os dados de input e output do enunciado para validar o caminho seguido.


A questão “consultas de soma de sub-sequências” é um exemplo que Francisco recentemente resolveu. O problema fornece uma lista de até duzentos mil elementos inteiros, cujo valor pode ser de zero até um bilhão, e um número m inteiro inferior ou igual a vinte. O objetivo é calcular o número de sub-sequências da lista fornecida cuja soma dos elementos seja divisível por m. O truque para resolução foi aplicar dois conceitos importantes: programação dinâmica e divisão e conquista. Primeiro, Francisco usou programação dinâmica para pré-calcular a quantidade de sub-sequências congruentes de zero até m-1 mod(m), para cada intervalo [l,r] de tamanho O(n) em tempo O(mn). Essa informação é armazenada em O(n) valores salvos. Em seguida, foi usada a técnica de divisão e conquista para dividir o intervalo [1,n] em dois subintervalos [1,mid] e [mid+1,n], e salvar as respostas para os subintervalos [left, mid] e [mid+1, right] em O(n) valores salvos, usando a informação pré-calculada pela programação dinâmica. O processo é repetido recursivamente para o subintervalo que contém a consulta, até que o intervalo seja reduzido a um único elemento. Por exemplo: seja a lista A = [5, 1, 3, 2], de quatro elementos, m = 3 e uma consulta do primeiro ao quarto elemento, logo as seguintes sub-sequências cuja soma dos elementos seja divisível por m são:

[5,1]

[3]

[1,2]

[5,1,3]

[1,3,2]

 

Em suma, Francisco aproveitou o período universitário para resolver diversos problemas de engenharia de software. Na ITAndroids, ele teve contato com aplicações de robótica, que envolvem uma maior proximidade do hardware e de imperfeições naturais comuns que dificultam essas aplicações, como latência de processamento, atrito, inércia ou erros de calibração. Nas competições de programação, Francisco se concentrou em desenvolver rapidamente algoritmos eficientes para resolver problemas matemáticos e computacionais complexos. Nos próximos meses, com o diploma do ITA concluído, com certeza Francisco estará muito bem preparado para brilhar no setor que decidir seguir, seja ele mais próximo do hardware ou puramente software.


-----

I had the pleasure of chatting with Francisco Bruno Dias Ribeiro Da Silva, a final year engineering student at the Instituto Tecnológico Aeronáutico (ITA) and software development leader at ITAndroids. We talked about his experiences optimizing algorithms for humanoid robot applications that play soccer autonomously, and his interest in programming competitions. 


Francisco had a great affinity for the area of exact sciences since elementary school, when he started participating in national mathematics competitions. As the years went by, his knowledge of solving complex mathematical problems improved, and he decided to study engineering at ITA, one of the most prestigious universities in Brazil.


After passing the difficult admission process to ITA, Francisco decided to dedicate himself extensively to learning software engineering. Besides programming classes and personal projects creating apps, Francisco also joined the software development team of ITAndroids. ITAndroids is a team of ITA students who create robots to play soccer autonomously in competitions such as the Robocup. It also promotes technological advancement in the area through relevant research and scientific publications, and has won several awards over the years.


One of Francisco's greatest contributions to his team's humanoid robot was the realization and optimization of an algorithm for calibrating the kinematic model of the robot's joints that influence the quality of its computer vision. This robot, approximately fifty centimeters tall, has a camera positioned on its head, which captures twenty images per second. An on-board software uses a Kalman filter sensory fusion technique, based on the data from the camera and the 9-axis inertial sensor (3D accelerometer, 3D gyroscope, and 3D magnetometer), to calculate the position, velocity, and orientation of the robot on the soccer field. The on-board software also performs the detection of important objects on the field, such as the goalposts, the field boundary lines, the ball, and others. However, if the joints of the robot are not perfectly calibrated, small errors of tenths of degrees in the positions of the joints' motor servos induce large errors, up to tens of centimeters, damaging the robot's performance.


The algorithm developed by Francisco is divided into two main parts. The first part consists in positioning the robot at a specific point on top of a customized carpet that has one hundred and twenty ArUco landmarks, whose positions are known. Data is collected by rotating the robot's neck approximately one hundred and eighty degrees for twenty seconds.


Then, for each ArUco landmark, the position measurements obtained are filtered, removing the values that are outside the range of plus or minus two standard deviations. The second part, consists of calculating the best fit coefficient of the angle of the motor servos present in the five joints responsible for this operation: three joints in the neck and two joints in the torso. The optimization algorithm to determine the five suitable angles is called Nelder-Mead. The objective is to find the correction coefficient for each joint, that is to determine the optimal kinematic model, which converges to the smallest error value between the real and measured position. Finally, with the result obtained by the program, it is necessary to apply the corrections to the mechanical systems. This process is repeated several times until a satisfactory result is achieved. The calibration program was written in the C++ language and compiled in g++ with specific flags, such as "-Ofast -fext-numericliterals -fPIC", for a better execution time and convenience during a competition.


Another project that Francisco is dedicated to is programming competitions, which can be on-site or remote. The Russian platform Code Forces, for example, regularly holds programming competitions, where not only the correct answers are evaluated, but also the performance of the program through its memory and execution time. For these reasons, the programs are mainly written in C++, and occasionally in other languages such as Python or Java. Francisco commented that it is important to read the statement carefully and understand the objective of the question. Then it is recommended to outline the main points of the resolution using the input and output data of the statement to validate the path followed.


The question “sub-sequence sum queries” is an example that Francisco recently solved. The problem provides a list of up to two hundred thousand integer elements, whose value can be from zero to one billion, and an integer number m less than or equal to twenty. The goal is to calculate the number of sub-sequences of the given list whose sum of elements is divisible by m. The trick to solving this was to apply two significant concepts: dynamic programming and divide and conquer. First, Francisco used dynamic programming to pre-calculate the number of congruent subsequences from zero to m-1 mod(m), for each interval [l,r] of size O(n) in time O(mn). This information is stored in O(n) saved values. Then, the divide-and-conquer technique was used to divide the interval [1,n] into two sub-intervals [1,mid] and [mid+1,n], and save the answers for the sub-intervals [left, mid] and [mid+1, right] into O(n) saved values, using the information pre-calculated by dynamic programming. The process is repeated recursively for the sub-range containing the query, until the range is reduced to a single element. For example: let be a list A = [5, 1, 3, 2], of four elements, m = 3 and a query from the first to the fourth element, then the following sub-sequences whose sum of elements is divisible by m are:

[5,1]

[3]

[1,2]

[5,1,3]

[1,3,2]


In summary, Francisco used his university period to solve numerous software engineering problems. At ITAndroids, he got in touch with robotics applications, which involve closer proximity to the hardware and common natural imperfections that difficult these applications, such as processing latency, friction, inertia, or calibration errors. In programming competitions, Francisco has focused on quickly developing efficient algorithms to solve complex mathematical and computational problems. In the coming months, with his ITA diploma completed, Francisco will surely be very well-prepared to shine in whatever industry he decides to pursue, be it closer to hardware or purely software.


Links: 

> Website do Francisco

> Paper do algoritmo de calibração

> App Pong Soccer

> ITAndroids

> Robocup

> OpenCV - Detection of ArUco markers

> Code Forces

> Code Forces - Subsequence Sum Queries

No comments:

Post a Comment