Algoritmos de agendamento eficientes para computação de dinâmicas inversas de robô em um sistema multiprocessador

O problema de agendar a computação de dinâmicas inversas do robô, consistindo em m módulos computacionais a serem executados em um sistema multiprocessador composto por p processadores homogêneos idênticos para alcançar um tempo de agendamento mínimo, é examinado. Este problema de agendamento é conhecido por ser NP-completo. Para alcançar o tempo de computação mínimo, as equações de movimento de Newton-Euler são expressas na forma de recorrência linear homogênea que resulta em alcançar o máximo paralelismo. Para acelerar a busca por uma solução, um algoritmo de busca heurística chamado de sucessores imediatos de maior nível dinâmico/primeiro (DHLF/MISF) é proposto para encontrar um agendamento rápido, mas subótimo. Para um agendamento ótimo, o problema de comprimento mínimo do agendamento pode ser resolvido por um método de busca em espaço de estados, o algoritmo A* acoplado a uma função heurística eficiente derivada do limite de Fernandez e Bussell.