Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: Relaxation-Based Search, From Everyday Life To Unfamiliar Territory, published by johnswentworth on November 10, 2021 on LessWrong.
Suppose I’m making plans to visit my parents for the holidays. I go online, and I book plane tickets. I do not worry about how I’m going to get to the airport - indeed, that question probably wouldn’t even enter my mind until a few days before the flight. Why not? Well, without thinking through any particular plan, I expect getting to the airport to be easy. There are many ways to get there (train, Uber/Lyft, drive & park) all of which I’ve used before and any of which would be fine.
This is relaxation-based search. I have a planning problem: visit my parents for the holidays. I’m searching for a plan which satisfies all my constraints: arrive at my parents’ house ~2-3 days before Christmas, arrive at the airport an hour before the plane takes off, don’t spend lots of time en route, don’t spend too much money, and many many other constraints (most of which are implicit in my head). In order to search efficiently, I relax the problem: I ignore many constraints which I expect will be easy to satisfy, like arriving at the airport on time or packing my bag. I throw out all but the hardest-to-satisfy constraints, which in this case mostly involve the plane tickets. I solve the “relaxed” search problem, with just the hardest constraints, then go back and tweak the plan to handle other constraints later.
Why This Matters: High-Dimensional Worlds
Our world is high-dimensional. Even a trip to visit my parents for the holidays involves hundreds of choices: dates, modes of transport, packing list, how early to arrive at the airport, etc. Multiply them all out, and we have an exponentially vast space of possibilities.
And that’s just a trip to visit my parents. Imagine the possibilities involved in designing a website or a scientific experiment!
When searching in spaces this large, we cannot afford to test every possibility. We are forced to rule out vast swaths of the search space without even looking at them. Relaxation-based search is one of the most general algorithms we know of which can do this.
The key is that we can usually express the problem-space using constraints which each depend on only a few dimensions. For instance, if I want to arrive at the airport an hour before the plane takes off, that constraint only involves two dimensions: my arrival time at the airport, and the takeoff time of the flight. It does not directly depend on what time I wake up, whether I pack a toothbrush, my parents’ plans, cost of the plane tickets, etc, etc.
So, if I can relax the problem to just a few of the most-difficult constraints, hopefully those constraints will involve a relatively small number of variables, and I can search through that smaller space more efficiently. When booking flights, for instance, I mostly just think about flight date, flight time, and cost (and maybe airline, sometimes, as a tiebreaker). I don’t worry about all the other dimensions, like packing my bag, getting to the airport, eating, buying presents for my parents, etc, etc.
Then, holding my solution for the most-taut constraints constant, I can go handle the other constraints. I plan around my flights to decide when to set my alarm, what/when to eat, and how to get to the airport. Each of those, in turn, only involves a few variables at a time, while holding the rest of the solution constant.
Tautness And Slackness
Imagine that I mistakenly think that the plane flight is an easy part of my holiday plans. I show up at the airport on December 22nd, find a service desk, and ask what flights are available.
This is likely to go poorly.
One crucial element to make relaxation-based search work well is to have an accurate idea of what’s hard, and what’s easy. Which constraints are “s...