artificial intelligence - AI de la propulsión de la nave espacial: aterriza una nave 3D en posición=0 y ángulo=0

artificial-intelligence game-physics (4)

Esta no es una respuesta, pero es demasiado larga para colocarla como comentario.

En primer lugar, una solución real implicará tanto la programación lineal (para la optimización multivariante con restricciones que se utilizarán en muchos de los subetapas) como las técnicas utilizadas en la optimización de trayectoria y / o la teoría de control. Este es un problema muy complejo y si puede resolverlo, puede tener un trabajo en cualquier empresa de su elección. Lo único que podría empeorar este problema serían los efectos de fricción (arrastre) o los efectos de gravitación externa del cuerpo. Una solución real también utilizaría idealmente la integración de Verlet o Runge Kutta de 4to orden, que ofrecen mejoras sobre la integración de Euler que ha implementado aquí.

En segundo lugar, creo que su "Segunda Versión Alternativa" de su pregunta anterior ha omitido la influencia de rotación en el vector de desplazamiento posicional que agrega a la posición en cada paso del tiempo. Mientras que los ejes del jet permanecen fijos en relación con el marco de referencia del barco, no permanecen fijos en relación con el sistema de coordenadas globales que está utilizando para aterrizar el barco (en la coordenada global [0, 0, 0] ). Por lo tanto, el vector [Px'', Py'', Pz''] (calculado a partir del marco de referencia del barco) debe someterse a una rotación apropiada en las 3 dimensiones antes de aplicarse a las coordenadas de posición global.

En tercer lugar, hay algunas suposiciones implícitas que no pudo especificar. Por ejemplo, una dimensión debe definirse como la dimensión de "profundidad de aterrizaje" y los valores de coordenadas negativas deben estar prohibidos (a menos que acepte un bloqueo de fuego). Desarrollé un modelo de maqueta para esto en el que asumí que z dimension era la dimensión de aterrizaje. Este problema es muy sensible al estado inicial y las restricciones impuestas a los jets. Todos mis intentos de usar las condiciones iniciales de ejemplo anteriores no se pudieron aterrizar. Por ejemplo, en mi maqueta (sin la rotación del vector de desplazamiento 3d mencionada anteriormente), las restricciones del chorro solo permiten la rotación en una dirección en el eje z. Entonces, si aZ vuelve negativo en cualquier momento (que a menudo es el caso), la nave se ve obligada a completar otra rotación completa en ese eje antes de que pueda intentar acercarse a cero grados otra vez. Además, sin la rotación vectorial de desplazamiento 3d, encontrará que Px solo se volverá negativo al usar las condiciones y limitaciones iniciales de su ejemplo, y la nave se verá obligada a estrellarse o divergir más y más en el eje x negativo mientras intenta maniobrar . La única forma de resolver esto es incorporar realmente la rotación o permitir suficientes fuerzas de reacción positivas y negativas.

Sin embargo, incluso cuando relajé sus limitaciones de fuerza mínima / máxima, no pude obtener mi maqueta para aterrizar con éxito, lo que demuestra que la planificación compleja probablemente será necesaria aquí. A menos que sea posible formular completamente este problema en el espacio de programación lineal, creo que necesitará incorporar una planificación avanzada o árboles de decisión estocásticos que sean lo suficientemente "inteligentes" como para usar continuamente métodos de rotación para reorientar los jets más flexibles hacia los ejes más necesarios actualmente. .

Por último, como señalé en la sección de comentarios, "el 14 de mayo de 2015, el código fuente de Space Engineers se puso a disposición del público de forma gratuita en GitHub". Si crees que el juego ya contiene esta lógica, ese debería ser tu lugar de partida. Sin embargo, sospecho que seguramente te decepcionará. La mayoría de las secuencias de aterrizaje de juegos espaciales simplemente toman el control de la nave y no simulan vectores de fuerza "reales". Una vez que tomas el control de un modelo 3-d, es muy fácil predeterminar una spline 3d con rotación que permitirá que la nave aterrice suavemente y con una orientación perfecta en el tiempo predeterminado. ¿Por qué un programador de juegos pasaría por este nivel de trabajo para una secuencia de aterrizaje? Este tipo de lógica podría controlar los misiles ICBM o los vehículos de reingreso del rover planetario y es simplemente exagerado en mi humilde opinión para un juego (a menos que el objetivo del juego sea ver si puedes aterrizar una nave espacial dañada con chorros arbitrarios y restricciones sin chocar) .

Este es un problema muy difícil sobre cómo maniobrar una nave espacial que se puede traducir y rotar en 3D, para un juego espacial.

La nave espacial tiene n jets ubicados en varias posiciones y direcciones.

La transformación del i -ésimo chorro en relación con el CM de la nave espacial es constante = Ti .

Transformation es una tupla de posición y orientación (cuaternión o matriz 3x3 o, menos preferible, ángulos de Euler).
Una transformación también se puede denotar con una sola matriz 4x4.

En otras palabras, todos los chorros están pegados a la nave y no pueden girar.

Un jet puede ejercer fuerza sobre la nave espacial solo en la dirección de su eje (verde).
Como resultado del pegamento, el eje giró junto con la nave espacial.

Todos los jets pueden ejercer fuerza (vector, Fi ) a una cierta magnitud (escalar, fi ):
i -th jet puede ejercer fuerza ( Fi = axis x fi ) solo dentro del rango min_i<= fi <=max_i .
Ambos min_i y max_i son constantes con valor conocido.

Para ser claros, la unidad de min_i , fi , max_i es Newton.
Ex. Si el rango no cubre 0, significa que el jet no se puede apagar.

La masa = m la nave espacial y el tensor de inercia = I
La transformación actual de la nave espacial = Tran0 , velocidad = V0 , angularVelocity = W0 .

El cuerpo físico de la nave espacial sigue reglas físicas bien conocidas:
Torque=rx F
F=ma
angularAcceleration = I^-1 x Torque
linearAcceleration = m^-1 x F

I diferente para cada dirección, pero por simplicidad, tiene el mismo valor para cada dirección (similar a una esfera). Por lo tanto, se I puede pensar como un escalar en lugar de una matriz de 3x3.

Pregunta

¿Cómo controlar todos los jets (todos fi ) para aterrizar la nave con la posición = 0 y el ángulo = 0?
Especificación matemática: Encuentre la función de fi(time) que tome un tiempo mínimo para alcanzar la position=(0,0,0) , orient=identity con velocity angularVelocity final y velocity = cero.

Más específicamente, ¿cuáles son los nombres de la técnica o algoritmos relacionados para resolver este problema?

Mi investigación (1 dimensión)

Si el universo es 1D (por lo tanto, sin rotación), el problema será fácil de resolver.
(Gracias a Gavin Lock , https://stackoverflow.com/a/40359322/3577745 )

Primero, encuentre el valor MIN_BURN=sum{min_i}/m MAX_BURN=sum{max_i}/m .

En segundo lugar, piense de manera opuesta, suponga que x=0 (posición) v=0 en t=0 ,
luego crea dos parábolas con x''''=MIN_BURN y x''''=MAX_BURN .
(Se supone que la segunda derivada es constante durante un período de tiempo, por lo que es una parábola).

El único trabajo restante es unir dos parábolas juntas.
La línea roja del tablero es donde se unen.

En el período de tiempo que x''''=MAX_BURN , todos fi=max_i .
En el período de tiempo que x''''=MIN_BURN , todo fi=min_i .

Funciona muy bien para 1D, pero en 3D, el problema es mucho más difícil.

Nota:
Solo una guía aproximada que me indica una dirección correcta es muy apreciada.
No necesito una IA perfecta, por ejemplo, puede llevar un poco más de tiempo que lo óptimo.
Lo pienso por más de 1 semana, todavía no encuentro ninguna pista.

Otros intentos / opiniones

No creo que el aprendizaje automático como la red neuronal sea apropiado para este caso.
La optimización de límite limitado por mínimos cuadrados puede ser útil, pero no sé cómo adaptar mis dos hiper-parábolas a esa forma de problema.
Esto se puede resolver usando muchas iteraciones, pero ¿cómo?
He buscado el sitio web de la NASA, pero no encuentro nada útil.
La característica puede existir en el juego "Space Engineer".
Comentada por Logman: el conocimiento en ingeniería mecánica puede ayudar.
Comentado por AndyG: Es un problema de planificación de movimiento con restricciones no holonómicas . Podría resolverse explorando rápidamente el árbol aleatorio (RRT) , la teoría en torno a la ecuación de Lyapunov y el regulador cuadrático lineal .
Comentado por John Coleman: Esto parece más un control óptimo que la IA.

Editar: "Suposición de cerca de 0" (opcional)

En la mayoría de los casos, AI (que se diseñará) se ejecuta continuamente (es decir, se llama cada paso de tiempo).
Por lo tanto, con la afinación de la IA, Tran0 suele ser casi identidad, V0 y W0 generalmente no son tan diferentes de 0, por ejemplo |Seta0|<30 degree , |W0|<5 degree per time-step .
Creo que la IA basada en esta suposición funcionaría bien en la mayoría de los casos. Aunque no es perfecto, puede considerarse una solución correcta (comencé a pensar que sin esta suposición, esta pregunta podría ser demasiado difícil).
Siento débilmente que esta suposición puede permitir algunos trucos que utilizan alguna aproximación "lineal".

La segunda pregunta alternativa: "Sintonizar 12 variables" (más fácil)

La pregunta anterior también se puede ver como sigue:

Quiero sintonizar los seis values y los seis values'' (1st-derivative) para que sean 0, usando la menor cantidad de time-steps.

Aquí hay una tabla que muestra una posible situación que AI puede enfrentar:

La tabla Multiplicador almacena la inertia^-1 * r mass^-1 de la pregunta original.

El multiplicador y el rango son constantes.

Cada paso de tiempo, se le pedirá a la IA que elija una tupla de valores fi que debe estar en el rango [min_i,max_i] por cada i+1 -jet.
Ex. Desde la tabla, AI puede elegir (f0=1,f1=0.1,f2=-1) .

Luego, la persona que llama usará fi para multiplicar con la tabla Multiplicador para obtener los values'''' .
Px'''' = f0*0.2+f1*0.0+f2*0.7
Py'''' = f0*0.3-f1*0.9-f2*0.6
Pz'''' = ....................
SetaX''''= ....................
SetaY''''= ....................
SetaZ''''= f0*0.0+f1*0.0+f2*5.0

Después de eso, la persona que llama actualizará todos los values'' con values'' += values'''' fórmula values'' += values'''' .
Px'' += Px''''
.................
SetaZ'' += SetaZ''''

Finalmente, la persona que llama actualizará todos los values con values de fórmula values += values'' .
Px += Px''
.................
SetaZ += SetaZ''

Se le pedirá a AI solo una vez por cada paso de tiempo.

El objetivo de AI es devolver tuplas de fi (puede ser diferente para diferentes pasos de tiempo), para hacer Px , Py , Pz , SetaX , SetaY , SetaZ , Px'' , Py'' , Pz'' , SetaX'' , SetaY'' , SetaZ'' = 0 (o muy cerca),
usando la menor cantidad de pasos de tiempo como sea posible.

Espero que proporcionar otra vista del problema lo haga más fácil.
No es exactamente el mismo problema, pero creo que una solución que puede resolver esta versión me puede acercar mucho a la respuesta de la pregunta original.

Una respuesta para esta pregunta alternativa puede ser muy útil.

La tercera pregunta alternativa - "Tune 6 Variables" (más fácil)

Esta es una versión simplificada con pérdida de la alternativa anterior.

La única diferencia es que el mundo ahora es 2D, Fi también es 2D (x, y).

Por lo tanto, tengo que sintonizar solo Px , Py , SetaZ , Px'' , Py'' , SetaZ'' = 0, usando la menor cantidad posible de pasos de tiempo.

Una respuesta a esta pregunta alternativa más fácil se puede considerar útil.

Para este tipo de problemas, hay dos técnicas disponibles: búsqueda de fuerza bruta y heurística. Bruteforce significa reconocer el problema como una caja negra con parámetros de entrada y salida y el objetivo es obtener los parámetros de entrada correctos para ganar el juego. Para programar dicha búsqueda de fuerza bruta, la gamefísica se ejecuta en un bucle de simulación (simulación física) y mediante búsqueda estocástica (minimax, alfa-beta-prunning) se prueban todas las posibilidades. La desventaja de la búsqueda de fuerza bruta es el alto consumo de CPU.

Las otras técnicas utilizan el conocimiento sobre el juego. Conocimiento sobre primitivas de movimiento y sobre evaluación. Este conocimiento está programado con lenguajes de computadora normales como C ++ o Java. La desventaja de esta idea es que a menudo es difícil comprender el conocimiento.

La mejor práctica para resolver la navegación de nave espacial es combinar ambas ideas en un sistema híbrido. Para programar el código fuente para este problema concreto, estimo que se necesitan casi 2000 líneas de código. Este tipo de problemas se hacen normalmente dentro de grandes proyectos con muchos programadores y toman alrededor de 6 meses.

Puedo introducir otra técnica en la combinación de (increíbles) respuestas propuestas.

Se basa más en la inteligencia artificial y proporciona soluciones cercanas a la óptima. Se llama Aprendizaje automático , más específicamente Q-Learning . Es sorprendentemente fácil de implementar pero difícil de acertar.

La ventaja es que el aprendizaje se puede hacer fuera de línea , por lo que el algoritmo puede ser súper rápido cuando se usa.

Podrías aprender cuando se construye el barco o cuando algo le sucede (destrucción del propulsor, trozos grandes arrancados ...).

Optimalidad

Observé que estás buscando soluciones casi óptimas. Su método con parábolas es bueno para un control óptimo. Lo que hiciste fue esto:

Observe el estado del sistema.
Para cada estado (llegando demasiado rápido, demasiado lento, alejándose, acercándose, etc.) ideó una acción ( aplicar una estrategia ) que llevará al sistema a un estado más cercano a la meta.
Repetir

Esto es bastante difícil de tratar para un ser humano en 3D (en demasiados casos, lo volverá loco), sin embargo, una máquina puede aprender dónde dividir las parábolas en cada dimensión, y diseñar una estrategia óptima por sí mismo.

El Q-learning funciona de manera muy similar a nosotros:

Observe el estado (secreto) del sistema
Seleccione una acción basada en una estrategia
- Si esta acción llevó al sistema a un estado deseable (más cercano al objetivo), marque el estado de acción / inicial como más deseable
Repetir

Discretice el estado de su sistema.

Para cada estado, tenga un mapa inicializado cuasialeatoriamente, que asigna cada estado a una Acción (esta es la estrategia ). También asigne una conveniencia a cada estado (inicialmente, cero en todas partes y 1000000 en el estado objetivo (X = 0, V = 0).

Su estado sería sus 3 posiciones, 3 ángulos, 3 velocidades de traslación y tres velocidades de rotación.
Tus acciones pueden ser cualquier combinación de propulsores

Formación

Entrenar a la IA (fase fuera de línea):

Genera muchas situaciones diversas
Aplicar la estrategia
Evaluar el nuevo estado
Deje que el algo (ver enlaces arriba) refuerce el valor de deseabilidad de las estrategias seleccionadas.

Uso en vivo en el juego

Después de un tiempo, surge una estrategia global para la navegación. Luego lo almacena, y durante su ciclo de juego simplemente muestra su estrategia y la aplica a cada situación a medida que surgen.

La estrategia aún puede aprender durante esta fase, pero probablemente más lentamente (porque ocurre en tiempo real). (Por cierto, sueño con un juego en el que la IA pueda aprender de los comentarios de todos los usuarios para que colectivamente podamos entrenarlo ^^)

Intenta esto en un simple problema 1D, desarrolla una estrategia notablemente rápida (unos pocos segundos).

En 2D, creo que se pueden obtener excelentes resultados en una hora.

Para 3D ... Estás viendo cálculos de un día para otro. Hay algunas cosas para intentar y acelerar el proceso:

Trate de nunca ''olvidar'' los cálculos anteriores, y alimentarlos como una estrategia inicial de ''mejor suposición''. Guárdalo en un archivo!
Podrías descartar algunos estados (¿como el rollo de nave, quizás?) Sin perder mucha capacidad de navegación pero aumentando la velocidad de cálculo en gran medida. Tal vez cambie los referenciales para que el barco esté siempre en el eje X, ¡de esta manera podrá soltar las dimensiones X e Y!
Los estados más frecuentemente encontrados tendrán una estrategia confiable y muy óptima. ¿Tal vez normalice el estado para hacer que su nave permanezca siempre cerca de un estado "estándar"?
Por lo general, los intervalos de velocidad de rotación pueden estar delimitados de forma segura (no se desea que un barco se mueva de forma impetuosa, por lo que la estrategia siempre será "desbobinar" esa velocidad). Por supuesto, los ángulos de rotación también están delimitados.
También es probable que pueda discretizar de forma no lineal las posiciones porque, más allá del objetivo, la precisión no afectará demasiado a la estrategia.

Trataré de mantener esto corto y dulce.

Un enfoque que se usa a menudo para resolver estos problemas en simulación es un árbol aleatorio de rápida exploración . Para dar al menos un poco de credibilidad a mi publicación, admitiré que los estudié, y la planificación del movimiento fue el área de especialización de mi laboratorio de investigación (planificación del movimiento probabilístico).

El documento canónico para leer sobre estos es Steven LaValle Exploración rápida de árboles aleatorios: una nueva herramienta para la planificación de caminos , y ha habido un millón de artículos publicados desde que todos lo mejoran de alguna manera.

Primero cubriré la descripción más básica de un RRT, y luego describiré cómo cambia cuando tienes restricciones dinámicas. Voy a dejar de jugar con eso después de usted:

Terminología

"Espacios"

El estado de tu nave espacial se puede describir por su posición tridimensional (x, y, z) y su rotación tridimensional (alfa, beta, gamma) (utilizo esos nombres griegos porque esos son los ángulos de Euler ).

El espacio de estado son todas las posiciones y rotaciones posibles en las que puede habitar tu nave espacial. Por supuesto, esto es infinito.

espacio de colisión son todos los estados "inválidos". es decir, posiciones realísticamente imposibles. Estos son estados en los que su nave espacial está colisionando con algún obstáculo (con otros cuerpos esto también incluiría la colisión consigo mismo, por ejemplo, la planificación de una longitud de cadena). Abreviado como C-Space.

el espacio libre es cualquier cosa que no sea espacio de colisión.

Enfoque general (sin restricciones dinámicas)

Para un cuerpo sin restricciones dinámicas, el enfoque es bastante sencillo:

Muestra un estado
Encuentre los vecinos más cercanos a ese estado
Intentar planificar una ruta entre los vecinos y el estado

Discutiré brevemente cada paso

Muestreo de un estado

Muestrear un estado en el caso más básico significa elegir valores aleatorios para cada entrada en su espacio de estado. Si hiciéramos esto con su nave espacial, tomaríamos muestra aleatoria de x, y, z, alfa, beta, gamma en todos sus valores posibles (muestreo aleatorio uniforme).

Por supuesto, mucho más de su espacio es el espacio de obstáculos que el espacio libre (porque generalmente confina su objeto en cuestión a algún "entorno" en el que desea moverse). Entonces, lo que es muy común hacer es tomar el cubo delimitador de su entorno y las posiciones de muestra dentro de él (x, y, z), y ahora tenemos muchas más posibilidades de muestrear en el espacio libre.

En un RRT, tomará muestras al azar la mayor parte del tiempo. Pero con cierta probabilidad, realmente elegirá su próxima muestra para ser su estado objetivo (juegue con ella, comience con 0.05). Esto se debe a que necesita probar periódicamente para ver si hay una ruta disponible desde el inicio hasta el objetivo.

Encontrar vecinos más cercanos a un estado muestreado

Eligió un entero fijo> 0. Llamemos ese entero k . Tus k vecinos más cercanos están cerca en el espacio estatal. Eso significa que tiene alguna medida de distancia que le puede decir qué tan lejos están los estados el uno del otro. La métrica de distancia más básica es la distancia euclidiana , que solo tiene en cuenta la distancia física y no le interesan los ángulos de rotación (porque en el caso más simple puede rotar 360 grados en un solo paso de tiempo).

Inicialmente, solo tendrá su posición inicial, por lo que será el único candidato en la lista de vecinos más cercanos.

Planificación de una ruta entre estados

Esto se llama planificación local . En un escenario del mundo real, usted sabe hacia dónde se dirige, y en el camino debe esquivar a otras personas y mover objetos. No nos preocuparemos por esas cosas aquí. En nuestro mundo de planificación, suponemos que el universo es estático, pero para nosotros.

Lo más común es asumir alguna interpolación lineal entre el estado muestreado y su vecino más cercano. El vecino (es decir, un nodo que ya está en el árbol) se mueve a lo largo de esta interpolación lineal bit por bit hasta que alcanza la configuración muestreada, o viaja una distancia máxima (recupere su métrica de distancia).

Lo que sucede aquí es que tu árbol está creciendo hacia la muestra . Cuando digo que pisa "poco a poco" me refiero a que define algún "delta" (un valor realmente pequeño) y avanza a lo largo de la interpolación lineal en cada paso de tiempo. En cada punto, verifica si el nuevo estado está en colisión con algún obstáculo. Si tocas un obstáculo, mantienes la última configuración válida como parte del árbol (¡no olvides almacenar el borde de alguna manera!) Entonces, lo que necesitarás para un planificador local es:

Comprobación de colisión
cómo "interpolar" entre dos estados (para su problema no necesita preocuparse porque haremos algo diferente).
Una simulación de física para el paso del tiempo (la integración de Euler es bastante común, pero menos estable que algo así como Runge-Kutta . ¡Afortunadamente ya tienes un modelo de física!

Modificación para restricciones dinámicas

Por supuesto, si suponemos que puede interpolar linealmente entre estados, violaremos la física que ha definido para su nave espacial. Entonces modificamos el RRT de la siguiente manera:

En lugar de muestrear estados aleatorios, tomamos muestras de controles aleatorios y aplicamos dichos controles durante un período de tiempo fijo (o hasta la colisión).

Antes, cuando probamos estados aleatorios, lo que realmente estábamos haciendo era elegir una dirección (en el espacio de estado) para movernos. Ahora que tenemos restricciones, tomamos muestras aleatorias de nuestros controles, que en realidad es lo mismo, excepto que tenemos la garantía de no violar nuestras limitaciones.

Después de aplicar su control por un intervalo de tiempo fijo (o hasta la colisión), agrega un nodo al árbol, con el control almacenado en el borde. Tu árbol crecerá muy rápido para explorar el espacio. Esta aplicación de control reemplaza la interpolación lineal entre estados de árbol y estados muestreados.

Muestreo de los controles

Tienes n jets que individualmente tienen alguna fuerza mínima y máxima que pueden aplicar. Muestra dentro de esa fuerza mínima y máxima para cada chorro .

¿A qué nodo (s) aplico mis controles?

Bueno, puede elegir al azar o puede sesgar la selección para elegir los nodos más cercanos a su estado objetivo (necesita la métrica de distancia). Este sesgo intentará hacer que los nodos se acerquen a la meta con el tiempo.

Ahora, con este enfoque, es poco probable que alcance exactamente su objetivo, por lo que debe definir una definición de "lo suficientemente cerca". Es decir, usará su métrica de distancia para encontrar los vecinos más cercanos a su estado objetivo y luego probarlos para "lo suficientemente cerca". Esta métrica "lo suficientemente cerca" puede ser diferente a su métrica de distancia, o no. Si usa la distancia euclidiana, pero es muy importante que la configuración de su objetivo también se gire correctamente, entonces puede modificar la métrica "lo suficientemente cerca" para observar las diferencias de ángulo.

Lo que es "lo suficientemente cerca" depende completamente de usted. También hay algo para que sintonices, y hay un millón de artículos que intentan acercarte mucho más en primer lugar.

Conclusión

Este muestreo aleatorio puede sonar ridículo, pero su árbol crecerá para explorar su espacio libre muy rápidamente. Vea algunos videos de YouTube en RRT para la planificación de rutas. No podemos garantizar algo llamado "integridad probabilística" con restricciones dinámicas, pero por lo general es "lo suficientemente bueno". A veces es posible que no exista una solución, por lo que tendrás que poner algo de lógica para detener el crecimiento del árbol después de un tiempo (20,000 muestras, por ejemplo)

Más recursos:

Comience con esto, y luego comience a buscar sus citas, y luego comience a investigar quién lo cita.