Predictable autopilot AI for a physics-based spaceship moving on a 2D plane

matskosan said:
With only translation, the implementation is easy - calculate the deceleration distance, accelerate until this distance to target, then decelerate.

I use this same approach for both angular and linear motion. Usually i try to keep acceleration constant, so the problem definition is target position, desired velocity at the target, current velocity, constant acc, constant decel. Then we can calculate the point in time when we need to switch from acceleration to deceleration to hit the target at desired velocity. Works for 6 dof the same way as for 1 dof.

But i see in your case the orientation also affects the direction of linear acceleration, and i can't commend on that.
I assume for space travel the planning reduces to the ideal trajectory to the target minimizing fuel, utilizing gravity of planets or moons.
Orientation can be likely ignored to calculate the trajectory, and after that the slight adjustments to keep ship orientation aligned to ideal trajectory are negligible.
Or in other words: Angular control seems more about error correction but usually isn't part of the control problem itself.

But it's not clear if that's the kind of problem you try to solve. Makes sense for solar system space travel planning and simulation, but not so much for space battle action / strategy games, i guess.
Maybe you want to give some examples of specific problems you have, otherwise it's hard to propose solutions to unknown problems. (But just saying - i doubt i could help even then, but others might.)

You certainly want to control position, but do you want to control the velocity and/or angle when you reach checkpoints or to optimize over different velocities and angles? Do you want to control angular velocity (e.g. to spin fast and spray unaimed weapon fire in all directions) and/or facing of the ship?

JoeJ said:

matskosan said:
With only translation, the implementation is easy - calculate the deceleration distance, accelerate until this distance to target, then decelerate.

I use this same approach for both angular and linear motion. Usually i try to keep acceleration constant, so the problem definition is target position, desired velocity at the target, current velocity, constant acc, constant decel. Then we can calculate the point in time when we need to switch from acceleration to deceleration to hit the target at desired velocity. Works for 6 dof the same way as for 1 dof.

But i see in your case the orientation also affects the direction of linear acceleration, and i can't commend on that.
I assume for space travel the planning reduces to the ideal trajectory to the target minimizing fuel, utilizing gravity of planets or moons.
Orientation can be likely ignored to calculate the trajectory, and after that the slight adjustments to keep ship orientation aligned to ideal trajectory are negligible.
Or in other words: Angular control seems more about error correction but usually isn't part of the control problem itself.

But it's not clear if that's the kind of problem you try to solve. Makes sense for solar system space travel planning and simulation, but not so much for space battle action / strategy games, i guess.
Maybe you want to give some examples of specific problems you have, otherwise it's hard to propose solutions to unknown problems. (But just saying - i doubt i could help even then, but others might.)

The specific problem is just that, as described in the original post - the ship that can aceelerate and rotate, with variying forward/backward/side accelerations, being able to reliably arrive at the target destination in a minimum possible time.

I'm trying to solve a more “local space” movement for now - the interplanetary travel is not out of the question, but is something for the future. I'm trying to create tactilal battles movement with predictable ship controls. Fuel weight is definitely not among the variables I would like to consider for movement calculations. Orientation is improtant both for combat (with ships having front and side facing weapons) and movement (front-facing thrusters are weaker than back-facing, and side-facing are the weakest). The action should evoke carrier movement, The Expanse, or Battlestar Galactica. There are other variables, such as decreased maneuverability on high speeds, but this is also for the later time when I am able to understand how to implent the simplest system…

@LorenzoGatti Eventually I would like to control velocities (both translational and angular) and orientation. For starters, maybe it would be simpler to have the implementation that controls just the position?

If you want physics-based movement, then you need some kind of control system to abstract that part from the navigation, same as in real vehicles (quadcopter drones are an example). You need something like a PID controller to adjust the thrusters dynamically so that the ship has the right speed and orientation.

There should be 3 modules:

• Global planner that does A* or something like that to plan a complete path to the final goal position. This path is made up of a series of intermediate goal positions. This module produces the next intermediate goal that is fed into the next module.
• Local motion planner that chooses the current high-level heading and speed that will reach an intermediate goal position. If your ships are non-holonomic (can't move in any direction i.e. like a car) then you have to do extra work here to control steering.
• PID controller to translate high-level desired motion into low-level thruster values. This may not be simple because you have multiple thrusters that interact, so it might involve solving a small system of equations.

I wouldn't focus on doing it in a “minimum possible time”, that's too difficult a problem. Physics-based movement is already challenging enough. Start with the local planning, and just kinematic control over vehicles (set velocities directly), then add the PID controller and finally global planner.

matskosan said:
the ship that can aceelerate and rotate, with variying forward/backward/side accelerations, being able to reliably arrive at the target destination in a minimum possible time.

I have some naive idea, which might be a start, but surely predictable at least:

The red arrow is the current velocity and position, the green arrow is target vel and pos.

To construct a trajectory you could use a Bezier curve.
1st and 4th control points are start and target pos, 2nd is start + start vel * k, 3rd is target pos + target vel * -k

k is some constant, of which i have no idea how to get it. Obviously it should be 1 to match velocities, but not sure if a Bezier spline is a proper way to represent physics at all.

Once the trajectory is calculated, following it wouldn't be hard.
Maybe you figure out a way to formulate an optimization problem, so an iterative approach could minimize the needed time.
Maybe you get some equation to describe the whole problem along the way, and you could use tools like Mathematica to find a closed form solution, which might exist or not.

I guess some people already tried to solve this before. Maybe NASA papers… : )

JoeJ said:
Maybe NASA papers… : )

My guess is that NASA is optimizing more for fuel usage than minimum time, so they are determining how to reduce the time that rockets are fired to get somewhere. This is why they use gravity of planets to increase speed by “slingshot” maneuvers, and also choose launch date precisely so that the planets are in the right places to do this.

I think it would be simpler and more flexible to use exponential smoothing to slowly change the speed and heading angle to the target values, than to use Bezier curves.

Hehe, NASA optimizes for fuel, Musk optimizes for time. Cuz he's a gamer and gets all the gov $$$ NASA might want \:D/

Hi @Aressera, thanks for your suggestions! I have already briefly tried a PID-based approach - it worked quite well for the orientation, but I got stuck when implementing the position control. Also there was an opinion that since all the variables of the system are known, its inputs can be calculated directly and PIDs are not necessary. Perhaps, I should have tried harder with the PIDs? I like your suggestion with controling the velocity directly, but in that case the problem collapses to the one where orientation is constant or acceleration is equal on all axes, and it is simple to solve.

I also have looked through some control theory / NASA papers and started to refresh my math and optimal control theory knowledge, but… this will take some time to make it right and be confident about it.

I found the following educational resources:

• Coursera course: Spacecraft Dynamics and Control.
• YouTube playlist with the same name - a course from Canada's Capital Univercity.
• A very expensive Spacecraft attitude control book.

Do you think any of those could be useful?

Typical real-world spacecraft control applies to enormous distances, days or weeks of travel, and slow maneuvers with a tight fuel budget: just about the opposite of an action game.

Instead of designing optimal control schemes, focus on respecting constraints and physical accuracy and on controlling the player's spaceship reliably and enemy spaceships with imperfections that the player can learn and exploit (e.g. tricking them into crashing or losing good positioning during a dogfight).

@matskosan How are you going with this? I'm trying to solve a very similar problem! Just without the goal of stopping on a position; more like passing through it with some desired velocity, and I also have orientation constraints like you (namely, at present, the ability to thrust only in a ship's forwards dir, for initial simplicity). As well as maximumDegPerSecond for rotation and maxSpeedChangePerSecond for linear movement (rather than going as far as trying to apply forces/accelerations, even if that's “better”. I have enough to worry about!). Trying to avoid real-life spaceship control theory as that seems nuts and way overkill when we could, potentially, touch velocity directly by “magic” but still respect constraints and give weighty movement.

I'm trying to change my iterative approach that kind of abuses my math functions to push the ship in a direction, eventually by way of clamping slowly chipping away at velocity's other directions until it's only going forwards, to something more numerical, kinda like what you're saying.

I'm thinking;

• We have current position P1 with initial velocity V1, and target position P2 (ideally with target velocity V2 but unsure how to use it atm)
• We find some velocity that gets us from P1 to P2 (somehow clamping to our linear speed limits)
• We calculate numTicks to turn to face opposite the velocity component we're trying to cancel out, then the number of ticks to actually cancel it out
• We repeat the same for the other velocity component
• Thus predicting the path becomes a few additions of time/ticks, and while it isn't a single equation, it's at least not 100% iterative (which is my current solution, and even one ship turning kills the frametime)

I'm not sure yet how to incorporate a target speed/velocity/direction into the point intersection, nor how to find the “optimal” path. How did you go? We can share notes and implementations if you'd like - I know how hard it can be to get assistance with such a weird problem! Cheers.

Two approaches that haven't been mentioned:

1) Implement your simulation in a way that allows you to compute gradients, for instance implementing it in Torch or TensorFlow, or using a C++ automatic differentiation library. Then you can write an objective function and optimize your path using gradient descent. I believe this is not far from how NASA optimizes trajectories.

2) Describe your problem as Gym environment (a Python class that inherits from gym.Env). You can then use Reinforcement Learning algorithms to train an agent that will solve any instances of your problem, for instance by picking a ready-made algorithm from Stable-Baselines3.

I've been playing around with 2) for the last few days and I think something like PPO (one of the RL algorithms implemented in Stable-Baselines3) would work well.

HateDread said:
As well as maximumDegPerSecond for rotation and maxSpeedChangePerSecond for linear movement (rather than going as far as trying to apply forces/accelerations, even if that's “better”. I have enough to worry about!). Trying to avoid real-life spaceship control theory as that seems nuts and way overkill when we could, potentially, touch velocity directly by “magic” but still respect constraints and give weighty movement.

If you depart arbitrarily from physical laws, your simulation will be more complicated because it will be a pile of hacks, more difficult to write because you won't be able or willing to follow established algorithms that do the right thing, less dependable because it will be incorrect with unnatural failure cases and exploits.

Particularly if you want to apply machine learning, you need the solid foundation of correct dynamics and straightforward equations.

@HateDread So far we went a maths way and implemented the required thrust calculation using third-degree Newtonian motion formulas - thrusters then change the applied acceleration linearly using constant jerk. This works fantastic for single axes but becomes complicated when for example maximum possible thrust on the velocity axis changes because of rotation, which causes ships to “overshoot” beyond the target and fly in circles. For now, such cases are ignored because it seems to be exactly what we need for player-controlled gameplay purposes… Later we will need to implement some sort of logic to control velocity on approach though.

@alvaro very curious about the approach you are taking with ML! I was thinking about applying some ML but unfortunately lack any knowledge in the area. Would be glad if you could share the results of your work.