4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If I were kid, I would prefer to seat near the window.. $\endgroup$ – koryakinp Oct 1 '18 at 17:24
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I went through "simulated annealing" and it is interesting. Many thanks for pointer; Will experiment further. $\endgroup$ – Aljo Jose Dec 20 '17 at 5:47
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I was thinking in a similar way. Can we reuse the learning from one episode, since there are different configuration of seat maps ? Also, how agent will know about re-seating families ? $\endgroup$ – Aljo Jose Dec 19 '17 at 12:13
  • $\begingroup$ If you define rewards properly, there will not be any problem. $\endgroup$ – OmG Dec 19 '17 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.