so I decided to make an autopilot for the lander based on what I felt like was the best strategy! Now I can have perfect landings every time without lifting a finger :D
Writing the autopilot code was a lot more fun than I expected! It felt a bit like programming a robot.
Source code: https://github.com/szhu/lunar-lander-autopilot
Original lander HN post: https://news.ycombinator.com/item?id=35032506
There's something timelessly appealing about lunar lander games. The very first game I ever played on a computer, written in BASIC, was a 'turn based' one dimensional lunar lander game where you input how much thrust you used for each second of the descent, and then it recalculated your altitude, velocity, etc. I learned programming by rewriting it to be a real-time game where you pressed a key to fire the engine.
Watching this auto pilot reminded me of landing Getaceiver on Barsoom in Heinlein’s Number of the Beast, which has a very long passage describing the (fictional) orbital mechanics landing on (a fictional alternate reality version of) Mars.
The autopilot did a perfect job of stopping the rotation and lateral motion, so the lander came down straight as an arrow. Unfortunately, the autopilot didn't even try to decelerate! I crashed into the moon at 0.9 degrees and 770 MPH.
https://github.com/szhu/lunar-lander-autopilot/blob/master/a...
I agree that the target velocity calculation is off though. I was excited that I came up with something reasonably theoretically correct for correcting rotation... and for figuring out when to fire the engines I just gave up and eyeballed it :)
Then you have stable baselines which implements popular reinforcement learning algorithms to solve these gym problems: https://stable-baselines3.readthedocs.io/en/master/
Shamless plug: I've built a series of games where you solve puzzles (2048) / toy problems (MDP) like the lunar lander using various AI and ML algorithms.
You can check it out here: https://ai-simulator.com/
In a way what I am building is a "general AI engine" that is capable of taking in an arbitrary game and play it, which is somewhat conceptually similar to how ChatGPT is a general AI that is able to solve a wide range of text-based tasks.
You can run PPO or DQN right now on the Open AI Gym implementation using Stable-Baselines3: https://stable-baselines3.readthedocs.io/en/master/
In fact I previously ran it locally and PPO solved the problem within 10 minutes of training with max reward of about 200.
In the real world, you would derive physics equations (acceleration -> velocity -> position), add constraints and then solve everything to obtain an optimal trajectory (mostly in term of fuel, but you can add other constraints too, for ex due to radar-ground or Antenna-Earth visibility). I wrote a blog post about Apollo's algorithm: https://blog.nodraak.fr/2020/12/aerospace-sim-2-guidance-law... (Described in the second section ; the first section is about a naive algorithm similar to yours that in the end did not work as well as I wanted).
Also, thanks for the code, I wanted to do the same, but lost motivation when I could not really expose in a satisfying way the internal state out of these JS modules (it's not complicated in the end, but I'm simply not a frontend dev ; and I wanted to avoid forking and monkey patching everything and simply adding some JS code throught the console or something).
Adding some realism to the engine physics (firing delays, minimum firing time, power ramp up, heat limits etc) would likely make it 10x harder.
If the distance to the moon was large, I would expect 4 phases:
1: Turn the lander towards the moon
2: Constant thrust towards the moon
3: Turn the lander away from the moon
4: Constant thrust away from the moon
But if the initial distance is small enough, turning it around might not be worth it or even possible.
So the optimal strategy is probably a somewhat complex function of the initial angle and distance to the moon.
time optimal landing lends techniques from bang-bang control (e.g. starting with v=0, max thrust towards the target, before flipping around half way and max thrust away from target)
fuel optimal landing (incuding RCS) technique would depend on the available time to turn retrograde (pointy end pointing away from direction of movement). if the duration before the decelerating burn is T1 (so t1 = t0+T1), the smallest possible rcs impulse would be applied so that at t1-T_st the lander is pointing retrograde (retrograde at t1), with T_st being the time needed to cancel the initial rcs impulse. For the deceleration of the lander, fuel optimal landing includes a single burn, constantly retrograde, so that at t_end the lander altitude is 0, and both the vertical and horizontal velocity components are 0.
The time t1 to start that burn depends on the maximum thrust available, the rate of mass change when firing the rocket (not modelled in the game), the initial velocity etc.
in this simple case, model predictive control is not needed, and an LQR (linear quadratic regulator) is sufficient to achieve optimality
source: rocket scientist with control theory background. I remember this example (a bit more realistically modelled) being a project during my studies
In doing this, it results in a few hundreds to thousands of solutions to test per timestep, which modern CPUs can shrug off easily. Not nearly as elegant as closed-form control theory systems, but easy to tune and give different goals.
chatgpt pointed me to the Gravity Turn altho it refused to give me a formula for it https://en.wikipedia.org/wiki/Gravity_turn#Deorbit_and_entry
Search for "fuel optimal rocket landing algorithm" for good starting points.
At least, that's what I thought, until I realized I had previously activated the auto-pilot. Best #footgun today (so far!).
So I guess I should say: > Oh SNAP! This auto-pilot is amazing at this!
Thanks!
The autopilot now scores a "perfect landing" almost every single time, it lands very noticeably faster, and the code no longer contains a complicated, trial-by-error formula!
I got my first 103+ point landing! (It does this about half the time now)
https://user-images.githubusercontent.com/1570168/224399420-...
https://www.youtube.com/watch?v=TY63i8V1-DA
The most I've used linear algebra since college:
https://github.com/Aperocky/ksp_eng/blob/master/lib/space_li...
https://twitter.com/_s_w_a_y_a_m_/status/1633468475611004928...
http://students.cs.ucl.ac.uk/schoolslab/projects/HT5/
from the readme here: https://github.com/ehmorris/lunar-lander
But unfortunately none of the lander's stats are exposed as global variables, so the only way I could make the autopilot was by modifying the existing code. (My commits are actually broken down exactly like this: a commit to expose the necessary variables globally, and another to actually add the autopilot.)
I would also love to be able to play it in the original game though, so I made a PR! I think it would be cool for it to be able to be activated as an easter egg.
How to you trigger autopilot on mobile?
“Unlike other arcade games, Lunar Lander does not feature a time limit; instead, the game starts with a set amount of fuel and inserting additional quarters purchases more fuel, allowing indefinite gameplay.“
https://en.m.wikipedia.org/wiki/Lunar_Lander_(1979_video_gam...
1.Step: Write code to simulate freefall of an object
2.Step: Write code to negate freefall of an object
https://user-images.githubusercontent.com/1570168/224370129-...
https://user-images.githubusercontent.com/1570168/224369935-...
