Mixed-Integer Programming

• Também chamado: MIP, MILP, MIQP, MICP
• Categoria: Planning & manipulation › Trajectory optimisation
• Tags: optimization, integer-programming, motion-planning, task-allocation, hybrid-systems

Otimização em que algumas variáveis precisam assumir valores inteiros, muitas vezes 0 ou 1, permitindo que um único problema combine escolhas discretas com grandezas contínuas.

Definição

Programação inteira mista (mixed-integer programming, MIP) é a otimização sobre uma mistura de variáveis contínuas e variáveis restritas a valores inteiros, na maioria das vezes variáveis binárias que assumem o valor 0 ou 1. As variáveis binárias codificam decisões discretas: por qual região um caminho passa, qual pé pisa em seguida, se um contato está ativo, qual robô assume qual tarefa. As variáveis contínuas carregam o resto, como posições, velocidades e forças. As classes comuns são nomeadas pela forma do problema restante: programas lineares inteiros mistos (MILP), programas quadráticos inteiros mistos (MIQP) e, de forma mais geral, programas convexos inteiros mistos (MICP).

Esses problemas são NP-difíceis em geral, mas os solvers modernos resolvem bem muitas instâncias práticas. Eles usam branch and bound (ramificação e limitação): resolver a relaxação contínua sem as exigências de integralidade, escolher uma variável que saiu fracionária, dividir em dois subproblemas que a forçam para baixo ou para cima, e podar qualquer ramo cuja relaxação já seja pior que a melhor solução inteira encontrada. Planos de corte apertam a relaxação ao longo do caminho. Solvers comerciais como Gurobi e CPLEX e de código aberto como SCIP, HiGHS e CBC implementam esses métodos.

A forma como um problema é escrito importa tanto quanto o solver usado. Condições lógicas são muitas vezes codificadas com restrições big-M, que ligam ou desligam uma restrição com uma variável binária e uma constante grande; uma constante grande demais enfraquece a relaxação e causa problemas numéricos. Formulações com relaxações apertadas são resolvidas muito mais rápido, o que é uma das razões pelas quais abordagens estruturadas como os grafos de conjuntos convexos são projetadas para que sua relaxação fique próxima do problema real.

Por que importa

Muitos problemas de planejamento robótico são em parte discretos: passar à esquerda ou à direita de um obstáculo, escolher uma sequência de contatos, atribuir tarefas. A programação inteira mista trata essas escolhas de forma exata dentro de uma única otimização, muitas vezes com um limite de quão longe a resposta está do ótimo, em vez de depender de heurísticas feitas à mão ou de amostragem.

Principais aplicações

• Planejamento de passos e de sequências de contato para robôs com pernas
• Planejamento de trajetórias através de regiões convexas para drones e braços robóticos
• Atribuição e agendamento de tarefas para frotas de robôs
• Controle preditivo baseado em modelo híbrido com modos discretos
• Planejamento de tarefas e movimento com escolhas discretas de ações

Na prática

Uma equipe que planeja os passos de um humanoide sobre pedras de travessia representa a superfície pisável de cada pedra como um polígono convexo. Para cada um dos próximos passos, ela adiciona variáveis binárias que selecionam em qual polígono o pé pisa, com restrições que só ficam ativas para o polígono escolhido, além de variáveis contínuas para as posições do pé e limites de comprimento de passo e de giro. O custo recompensa o avanço em direção à meta e penaliza passos desajeitados. Um solver inteiro misto retorna uma sequência de passos, geralmente dentro de um limite de tempo definido para o replanejamento, junto com o gap entre a melhor solução encontrada e o melhor limite. Se os tempos de solução forem longos demais, a equipe reduz o número de passos planejados de uma vez, aperta os valores de big-M ou faz warm start a partir do plano anterior.

Equívocos comuns

• Programas inteiros mistos são sempre lentos demais para a robótica — problemas pequenos e bem formulados podem ser resolvidos rápido o suficiente para replanejamento online
• Arredondar a relaxação contínua dá a solução inteira ótima — o arredondamento pode ser inviável ou ficar longe do ótimo, a menos que a relaxação seja apertada
• Qualquer valor grande de M funciona em restrições big-M — valores grandes demais enfraquecem a relaxação e causam dificuldades numéricas
• Um solver que para no limite de tempo falhou — ele geralmente retorna a melhor solução até então e um gap de otimalidade que diz quão boa ela é

Quem deve saber

• Engenheiros de planejamento de movimento e de passos
• Desenvolvedores de agendamento de frotas e alocação de tarefas
• Pesquisadores de controle baseado em otimização
• Estudantes de robótica que estudam otimização

Tecnologias relacionadas

• Branch and Bound
• Gurobi
• SCIP
• HiGHS
• Programação linear (Linear Programming)
• Otimização convexa (Convex Optimization)

Termos relacionados

• Graph of Convex Sets
• Task and Motion Planning
• Model Predictive Control
• Motion Planning
• Trajectory Planning
• Multi-Agent Path Finding

Projetos relacionados

• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
• GTSAM: Factor-graph optimization library powering many modern SLAM backends
• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• PyPose: PyTorch library for differentiable robotics with deep learning and Lie group optimization

Vídeos

• Mixed Integer Linear Programming (MILP) Tutorial: APMonitor.com

Wikipédia

• Programação inteira