El término planificación de movimiento (del inglés motion planning) es aplicado para describir un conjunto de problemas que están relacionados con mover un objeto (robot) de un punto inicial a un punto final evitando colisionar con los posibles obstáculos del entorno.[1] Para el análisis de estos problemas suele utilizarse el espacio euclidiano en dos dimensiones y en ocasiones se considera que la colisión con un obstáculo sólo ocurre con los puntos internos de este (asumiendo a los obstáculos como polígonos simples) y no con la frontera, aunque en términos prácticos puede no resultar seguro que un robot pase tan cerca de un obstáculo.La descomposición en celdas exactas es utilizada para representar el espacio libre de obstáculos, una vez que se conoce basta con calcular una ruta a través de este espacio.La construcción de un mapa trapezoidal se realiza tomando un conjunto de polígonos disjuntos, estos son encerrados en una caja para delimitar el espacio en que se crearán los trapezoides.A continuación se trazan líneas verticales en los vértices de cada polígono hasta que la línea alcanza algún obstáculo, ya sea la frontera de algún polígono o la «caja».En este algoritmo las celdas corresponden a los elementos formados por una rejilla de tamaño fijo, en este caso los obstáculos son representados como celdas completamente ocupadas.
Descomposición en celdas exactas usando mapa trapezoidal
