Is reseating passengers a reinforcement learning problem?

Question

Requirement is to optimally move passengers from one seat map to another which has a different configuration.

Move should be based on many rules like -
1) Families should be sitting together
2) Those who were at windows seat should be moved to window seat if available.
3) Kids should be seated at middle seat.
4) and many more..

There are many seat map configurations available and at a time we need to move passengers from one to another as per the requirement.

Is it a reinforcement learning problem ? If yes, how it can be approached.

Answer 1

Reinforcement learning is more about interacting with an environment, and while this could be posed as an RL problem, I think using Global Optimization would be a more direct approach.

Essentially you want to design a cost function that describes how good a particular seating is and then use it to search the space of possible seatings.

For example to solve the problem with Simulated Annealing:

1. Design a cost function $e(s)$ that measures how good a seating arrangement is. Lower cost means better seating.

2. Design an acceptance probability function $P(e, e', T)$ that takes the costs of seating arrangements $s$ and $s'$, and a temperature $T$, and returns a probability $P$ with the properties (a) $P>0$ even if $s'$ is worse than $s$ (b) the better $s'$ is relative to $s$, the higher $P$ is and (b) the lower the temperature, $T$, the close $P$ is to $0$ when $s'$ is worse than $s$.

3. Set some large initial $T$ and design an annealing schedule for decreasing $T$ with the number of iterations.

4. Start with some seating arrangement $S$. This can be random or chosen according to a greedy strategy that tries to satisfy as many constraints as possible.

5. Repeat for $i$ in $k$ steps (for some sufficiently large $k$):

   • Consider a neighboring state $S'$ that can be reached by randomly swapping two seated people or moving someone to an empty seat. Set $S$ to $S'$ with probability $P(S, S', T)$

   • Decrease $T$ according to the annealing schedule at step $i$

The simulation starting at (4) can be run once or many times saving only the best result. At the end you should arrive at close to or exactly the best possible seating arrangement.

Answer 2

Yes. It can be. For reinforcement learning you need States, Actions and Rewards to run a reinforcement algorithm on a situation.

States are seats, Actions are moving a person from a seat to another seat, and Rewards are born from specified rules.

For example, moving a baby to a windows seat could have $-\infty$ reward (or you can prevent to do this action and exclude it from the possible action).