Mixed-Integer Programming
- También llamado: MIP, MILP, MIQP, MICP
- Categoría: Planning & manipulation › Trajectory optimisation
- Etiquetas: optimization, integer-programming, motion-planning, task-allocation, hybrid-systems
Optimización en la que algunas variables deben tomar valores enteros, a menudo 0 o 1, lo que permite que un mismo problema combine elecciones discretas con magnitudes continuas.
Definición
Programación entera mixta (mixed-integer programming, MIP) es la optimización sobre una mezcla de variables continuas y variables restringidas a valores enteros, la mayoría de las veces variables binarias que toman el valor 0 o 1. Las variables binarias codifican decisiones discretas: por qué región pasa un camino, qué pie se apoya a continuación, si un contacto está activo, qué robot se encarga de qué tarea. Las variables continuas llevan el resto, como posiciones, velocidades y fuerzas. Las clases habituales se nombran según la forma del problema restante: programas lineales enteros mixtos (MILP), programas cuadráticos enteros mixtos (MIQP) y, de forma más general, programas convexos enteros mixtos (MICP).
Estos problemas son NP-difíciles en general, pero los solvers modernos resuelven bien muchos casos prácticos. Usan ramificación y acotación (branch and bound): resolver la relajación continua prescindiendo de los requisitos de integralidad, elegir una variable que haya salido fraccionaria, dividir en dos subproblemas que la fuerzan hacia abajo o hacia arriba, y podar cualquier rama cuya relajación ya sea peor que la mejor solución entera encontrada. Los planos de corte ajustan la relajación por el camino. Solvers comerciales como Gurobi y CPLEX y de código abierto como SCIP, HiGHS y CBC implementan estos métodos.
Cómo se escribe un problema importa tanto como qué solver se usa. Las condiciones lógicas suelen codificarse con restricciones big-M, que activan o desactivan una restricción con una variable binaria y una constante grande; una constante demasiado grande debilita la relajación y causa problemas numéricos. Las formulaciones con relajaciones ajustadas se resuelven mucho más rápido, y esa es una de las razones por las que enfoques estructurados como los grafos de conjuntos convexos se diseñan para que su relajación esté cerca del problema real.
Por qué importa
Muchos problemas de planificación robótica son en parte discretos: pasar por la izquierda o por la derecha de un obstáculo, elegir una secuencia de contactos, asignar tareas. La programación entera mixta maneja estas elecciones de forma exacta dentro de una sola optimización, a menudo con una cota de lo lejos que está la respuesta del óptimo, en lugar de depender de heurísticas hechas a mano o del muestreo.
Aplicaciones clave
- Planificación de pisadas y de secuencias de contacto para robots con patas
- Planificación de trayectorias a través de regiones convexas para drones y brazos robóticos
- Asignación y programación de tareas para flotas de robots
- Control predictivo basado en modelo híbrido con modos discretos
- Planificación de tareas y movimiento con elecciones discretas de acciones
En la práctica
Un equipo que planifica las pisadas de un humanoide sobre piedras de paso representa la superficie transitable de cada piedra como un polígono convexo. Para cada uno de los próximos pasos, añaden variables binarias que seleccionan en qué polígono se apoya el pie, con restricciones que solo están activas para el polígono elegido, además de variables continuas para las posiciones del pie y límites en la longitud del paso y en el giro. El coste premia el avance hacia la meta y penaliza los pasos incómodos. Un solver entero mixto devuelve una secuencia de pasos, normalmente dentro de un límite de tiempo fijado para la replanificación, junto con la brecha entre la mejor solución encontrada y la mejor cota. Si los tiempos de resolución son demasiado largos, el equipo reduce el número de pasos planificados a la vez, ajusta los valores big-M o hace un arranque en caliente desde el plan anterior.
Ideas erróneas comunes
- Los programas enteros mixtos son siempre demasiado lentos para la robótica — los problemas pequeños y bien formulados pueden resolverse lo bastante rápido para replanificar en línea
- Redondear la relajación continua da la solución entera óptima — el redondeo puede ser no factible o estar lejos del óptimo a menos que la relajación sea ajustada
- Cualquier valor grande de M sirve en las restricciones big-M — los valores excesivamente grandes debilitan la relajación y causan dificultades numéricas
- Un solver que se detiene en su límite de tiempo ha fallado — normalmente devuelve la mejor solución hasta el momento y una brecha de optimalidad que indica lo buena que es
Quién debería saberlo
- Ingenieros de planificación de movimiento y de pisadas
- Desarrolladores de programación de flotas y asignación de tareas
- Investigadores en control basado en optimización
- Estudiantes de robótica que estudian optimización
Tecnologías relacionadas
- Ramificación y acotación (Branch and Bound)
- Gurobi
- SCIP
- HiGHS
- Programación lineal (Linear Programming)
- Optimización convexa (Convex Optimization)
Términos relacionados
- Graph of Convex Sets
- Task and Motion Planning
- Model Predictive Control
- Motion Planning
- Trajectory Planning
- Multi-Agent Path Finding
Proyectos 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