3

I have to code AI to control many propulsion jets for a spaceship in a game.

For simplicity :-
Let the space be 1D.
Spaceship is a point and there is only 1 jet.

Rule and problem

Let x, v and a are position, velocity, acceleration of the spaceship.
Let F be the force of jet that apply to the ship.

I know mass m of the spaceship, let's say m=1.

Here is a summary :-

acceleration = F/m;
v = vOld + acceleration*timestep;
x = xOld + v*timestep;

The objective is to land the ship on a certain position with 0 velocity :- x=0 and v=0.

AI can "accelerate" or "decelerate" the jet :-

F+=flexibility;
or 
F-=flexibility;

AI can access current x, v and F. AI can also cache it.

How should I program the AI?

My poor solution

Idea 1 : At last, x should = 0.

Assume that a is constant :-

(current x) + (current v) * t + 1/2 * a * t * t = 0

t is a magic number - how much time its require to make the spaceship's x=0.

Idea 2 : At last, v should = 0.

(current v) + a*t = 0

I mixed both ideas :-

if |x|>=thresholdX --> use idea 1
if |x|~0 --> use idea 2
in between --> weight average of 2 ideas

Here, thresholdX is another magic number.
I use a from the equation to find appropriate F. (F=ma)

Here is a result :-

enter image description here
The graph is noisy because the mass is approximated by another AI, and there are some small random external forces.

If anybody asks, I can post my C++ code (~100 lines).

javaLover
  • 6,347
  • 2
  • 22
  • 67
  • 1
    Doing it with a constant `a` is pretty much impossible -- for each `x` there is only one possible `v` that would allow a smooth landing, and for each `v` there is only one `x`. You will need a variable acceleration, `a(t)`. – pingul Nov 01 '16 at 10:42
  • @pingul Great idea, thank! May you guess what should be the formula of function `a(t)`? – javaLover Nov 01 '16 at 10:43
  • 1
    It can be a quite tricky problem. Finding the analytical solution (i.e. the definite form of `a(t)`) is hard because there are infinitely many solutions that achieves the end result (`v == 0` when `x == 0`). A less mathy solution could be to either train it with some learning algorithm or make a regulatory control system, but these can be difficult as well. I outlined a somewhat simpler method here : http://stackoverflow.com/questions/38870822/how-to-implement-arriving-behavior-with-time-delta/38880776#38880776 – pingul Nov 01 '16 at 10:52
  • @pingul Superb link! A link in the page you linked ( http://natureofcode.com/book/chapter-6-autonomous-agents/ ) is very good, thank! – javaLover Nov 01 '16 at 11:11
  • This isn't a solution, but to better understand the problem, maybe you should plot your variables in [phase space](https://en.wikipedia.org/wiki/Phase_space) rather than against time. For example you can create a `v-x` graph and plot the area from which you can make a safe landing given a maximum value of `a` (basically your rocket's maximum thrust). – biziclop Nov 01 '16 at 11:57
  • Why are you formulating the problem as "an AI problem", instead of "control systems problem"? – fest Mar 17 '19 at 18:22
  • @fest At that time, I just wanted to use it for AI enemy in a game, and I didn't know the cool technical word "control systems problem" yet. – javaLover Mar 18 '19 at 03:25

2 Answers2

4

Firstly - Are you planning on landing on a body (which has mass), or just coming to a stop at some arbitray point in space? Your question says "land", so I'm assuming the former, in which case you need to factor gravity in as well. Which should be easy enough to do: F_actual = F_engine - F_gravity.

Secondly - How would you do this in real life? Real-life pilots want to "establish" their aircraft on a "glide slope" (well before reaching the runway), with the aircraft "trimmed" so that in ideal conditions (no wind, etc) the plane could land itself with no control inputs (I'm simplifying a bit, and ignoring flare etc.)

For a rocket, I would probably want to get myself into a situation such that at some safe height above the ground, my descent rate is such that with the engine running at some constant power, the rocket would settle to the ground by itself, with no extra input from me except killing the engine at the point of touchdown. (Actually, I would hope that the flight system allowed me to arm an auto-kill on touchdown.)

To see how this would work, just run the problem in reverse. Starting at x=0, v=0, with a=some constant and reasonable acceleration that the engine can produce, plot the x and v over time as the rocket ascends. Obviously, v=at (a line) and x is a summation of those values (a parabola).

That parabola is your "glide slope". Now rather than trying to get x=0 and v=0 at the same time (without x ever becoming negative), your problem has become "How do I hit the glide slope at a safe height?". So your logic would be something like:

  1. If x=0, kill engine.
  2. Else, if you are on the glide slope, set engine power for desired (constant) decel. Sit back and wait while physics does all the hard work for you.
  3. Else, if x < min_approach_height and you are not on the glide slope, burn hard enough to climb.
  4. Else, adjust engine power to reach the glide slope.

Some notes:

  1. By "glide slope", I don't mean to imply horizontal motion. I'm just using the term by analogy to fixed wing aircraft. What I mean is the plot of v against x that allows a constant a to produce a gentle touch-down with no additional control inputs.
  2. Does the body you're landing on have an atmosphere? If so, your rocket would have a terminal velocity, in which case the logic simplifies to: enter the atmosphere fast enough to hit terminal velocity above the glide slope. Wait for the glide slope. As you hit the slope, fire the engines at constant power. Kill the engine as you kiss the ground.
  3. Until now, I've disregarded the "approximated" mass and the "random external forces". As long as these don't lead you too far away from the glide slope, small adjustments to power should bring you back to the slope. Make these corrections continuously as you descend. If you ever deviate too far from the slope, MAX BURN and try again.
  4. Incidentally, if it weren't for those random effects, this glide slope approach makes it fairly simple to land gently with an engine that has only two settings, constant deceleration power and off.
  5. I haven't solved your problem, just turned it into a different problem - BUT, solving this new problem should make your game a little more realistic (hopefully improving immersion). Also, this problem may end up being simpler than the original (see notes 2 and 4 above). And, lastly, setting up on the glide slope early, and then only making small correction adjustments means that your AI doesn't have to handle extreme situations, or provide extreme control inputs.

Hmmmm - even after editing, this post is quite long. I think I should stop right about..... now.

Allison Lock
  • 2,375
  • 15
  • 17
  • Cool! I applied your solution and it works perfectly. Now I tried to extend this solution to 3D, and I stuck. Here is a link to the new question. You may be also able to answer that easily. Thank for taking a look! http://stackoverflow.com/questions/40623315/ai-of-spaceships-propulsion-land-a-3d-ship-at-position-0-and-angle-0 – javaLover Nov 19 '16 at 04:01
0

The first step is to implement the game with manual control. Build a simulation with physics and make some buttons for the pilot. If manual landing of the spaceship works than its time for the first AI-prototype. This is commonly implemented as a one-armed bandit, that means a random generator calculates the acceleration. The user has no other possibility than watch and hope. The next AI prototype which will also be implemented by hand uses a pseudorandom-generator. That means, the burst is in a certain range but remains randomly. The question is not, if the AI is able to land, the question is: need the AI 10 trials or 100 trials. The best practice for reducing failure-rate is to use rules like in the OP. These heuristics don't work in every situation they can only improve the pseudo-random-generator. It is a little bit like procedural generation.

Manuel Rodriguez
  • 734
  • 4
  • 18
  • Should numbers from pseudorandom-generator be used for some system setting? Which ones in what formula? Do you mean something like `std::mt19937`? Do I have to randomly pick seed? – javaLover Nov 02 '16 at 03:52
  • The AI can control F (force to spaceship). Version 1 of the AI is to fluctuate F between -100 and 100 (true random generator). The spaceship will drive on a random walk. Version 2 of the AI is to generate F with reduced randomness "between 0 and 10, but if position x > 0 then give F=-10". Version 3 of the AI is to reduce the randomness further. That is called a pseudorandom-generator. It is a hybrid-system (heuristics plus C++ randomgenerator). – Manuel Rodriguez Nov 02 '16 at 14:06