Solving planning problems

Question

I'm new to the AI/ algorithm field and is currently trying to solve a problem, I've so far only implemented an A* pathfinding on a 2d grid array before.

The problem goes like this:

Consider a class of 40 students (20f,20m) with varying height and have their own seating preferences(row, column, or both), and a classroom 50 seats, each student must occupy a seat and the seats are being laid out as follow:

[ ] [ ] [ ]   [ ] [ ] [ ] [ ]   [ ] [ ] [ ]

[ ] [ ] [ ]   [ ] [ ] [ ] [ ]   [ ] [ ] [ ]

[ ] [ ] [ ]   [ ] [ ] [ ] [ ]   [ ] [ ] [ ]

[ ] [ ] [ ]   [ ] [ ] [ ] [ ]   [ ] [ ] [ ]

[ ] [ ] [ ]   [ ] [ ] [ ] [ ]   [ ] [ ] [ ]

              [ WHITEBOARD ]

To ideally seat them, a scoring graph has been elected:

No students seating directly in front: +4 points

Student seating directly in front is shorter by at least 2cm: +4 points

Student seating beside you is of the opposite sex: +8 points

4 students of the same gender occupying a column: -10 points

A column with ascending height from the whiteboard: +20 points

Seating according to individual preferences: +2 points

The goal is to score the maximum points possible.

My idea is to use A* modified to suit the current problem:

• Starting: all students unseated
• Path cost: increment of points after the transition
• Goal: all students seated

The problem here is, the maximum points possible is not known, and I can foresee that there might be scenario where the program fails to plan, (the program might pick +8 and then followed by +4, whereas a better way will be to pick +2 then followed by +20), I am aware that I can look for certain depth, say a depth of 5. This invites another question: what's the depth that I should use? I don't want to visit all the possible states.

1. How hard is this kind of problem? (from a scale of solving the maze to solving chess/go)

2. Am I on the right path of solving this problem?

Answer 1

Constraint 6 looks like it implies that this problem might be NP-complete or NP-hard. That means: the A* algorithm won't succeed in this, because it's impossible (unless P = NP) to create a good admissible heuristic function. Without constraint 6, a First Fit Decreasing algorithm can be designed to be optimal:

• All even seats go to females, all odd seats go to males (if there are not enough seats for 1 gender, add the overflow in the other gender). List both independently. While listing 1 gender, ignore the seats of the other gender.

• Sort of all students in 1 gender group according to height. Assign them one by one in decreasing height.

• For each step, allot the largest unassigned student to the unassigned seat at the highest row (and secondarily the most on the left)