Review please: problem / domain model / constraints for astronomical observation scheduling

16 views
Skip to first unread message

Adalbert Schwafel

unread,
Jul 21, 2021, 1:00:20 PM7/21/21
to OptaPlanner development
Hi, 

I am taking a 2nd attempt at Opta to solve astronomical observation scheduling after focussing more into the Choco constraint solver. I would very much appreciate your comments whether the approach taken is ok, and scalable. So far, Choco seems to be much much faster and I wonder if I am modelling my problem poorly in Opta. I see the advantage of Opta in simpler expression of constraints. Benchmarking seems to indicate that I should be using FIRST_FIT / TABU_SEARCH. I only have 5 constraints.

Any comment what could be improved is greatly appreciated. Thanks a lot !

Problem
- ~ 3000 Observations (OBs) are scheduled to time slots in nights by assigning the start slot
- There is a total of 180 nights
- each night has 20 time slots of 30min
- OBs have variable duration and may need one ore several time slots
- OBs belong to observing runs. If they are "visitor mode", i.e somebody travels to the mountain, additional constraints apply.
- the time slots in the below domain model are precomputed and assigned to the solution

Domain Model (snippet in Groovy)
@PlanningEntity
public class OB {
    @PlanningVariable(nullable = false, valueRangeProviderRefs = "timeslotRange")
    Timeslot start 
    @PlanningId
    int obId
    int runId // OB belongs to an observing run
    boolean[] observable // whether the OB is observable in time slot n
    int reqNoOfSlots // the required number of slots for this observation
    EObservingMode observingMode

    int getStartSlot() {
        start.slot
    }

    int getEndSlot() {
        start.slot + reqNoOfSlots - 1
    }

    
    int getNight() {
        startSlot.intdiv(SLOTS_PER_NIGHT)
    }

    // compute a chunk ID that is unique per run per night
    int getChunkID() {
        1000 * runId + getNight()
    }

    
    boolean isVisitor() {
        observingMode == EObservingMode.Visitor
    }
}

class Timeslot {
    @PlanningId
    int slot
    Date start
    Date end
   ...
}

@PlanningSolution
class Schedule {
    @ValueRangeProvider(id = "timeslotRange")
    @ProblemFactCollectionProperty
    List<Timeslot> timeslots

    @PlanningEntityCollectionProperty
    List<OB> observations

    @PlanningScore
    HardSoftScore score
}


Constraints
// OBs must not overlap
Constraint noOverlap(ConstraintFactory factory) {
    factory.fromUniquePair(OB.class,
        overlapping(ob -> ob.startSlot, ob -> ob.endSlot + 1))
        .penalize("overlap", HardSoftScore.ONE_HARD)
}


// OBs must be observable
Constraint observable(ConstraintFactory factory) {
    factory.from(OB.class)
        .filter(ob -> !ob.observable[ob.startSlot])
        .penalize("not observable", HardSoftScore.ONE_HARD)
}


// in any given night, visitor mode OBs of the same run must be consecutive with no gaps
Constraint consecutiveVMChunks(ConstraintFactory factory) {
    factory.from(OB.class).filter(ob -> ob.visitor)
        .groupBy(OB::getChunkID,
            min(OB::getStartSlot as Function),
            max(OB::getEndSlot as Function),
            sum(OB::getReqNoOfSlots as ToIntFunction))
        .filter((chunk, minStart, maxEnd, noOfSlots) -> maxEnd + 1 - minStart > noOfSlots)
        .penalize("non-consecutive VM chunk", HardSoftScore.ONE_HARD)
}

// in any given night, OBs of not more than 2 different visitor mode runs my be scheduled
Constraint onlyTwoVMChunksPerNight(factory) {
    factory.from(OB.class).filter(ob -> ob.visitor)
        .groupBy(OB::getNight, countDistinct(OB::getRunId as Function))
        .filter({ night, noOfRuns -> noOfRuns > 2 })
        .penalize("only 2 VM runs per night", HardSoftScore.ONE_HARD)
}


// total duration of a visitor mode run must not exceed 2 * required number of slots
Constraint maxVMRunLength(ConstraintFactory constraintFactory) {
    constraintFactory.from(OB.class).filter(ob -> ob.visitor)
        .groupBy(OB::getRunId,
            min(OB::getStartSlot as Function),
            max(OB::getEndSlot as Function))
        .filter((runId, minStart, maxEnd) -> 
            maxEnd + 1 - minStart > 2 * TatooSolver.vmRunLengths[runId])
        .penalize("VM run must be shorter", HardSoftScore.ONE_HARD)


Radovan Synek

unread,
Jul 22, 2021, 8:52:46 AM7/22/21
to OptaPlanner development
Hello,

would you please provide the INFO logging output? It shows the score calculation speed.

by looking at the constraints I noticed they always penalize by HardSoftScore.ONE_HARD. While it's correct, it does not distinguish between an Observation that slightly breaks a constraint and an Observation that breaks it a lot.

When there is a certain threshold that tells if a constraint is broken, usually inside the .filter() call, penalizing for the difference between the actual amount and the threshold gives OptaPlanner more information about how good or bad the solution is.

For example:

Constraint onlyTwoVMChunksPerNight(factory) {
    factory.from(OB.class).filter(ob -> ob.visitor)
        .groupBy(OB::getNight, countDistinct(OB::getRunId as Function))
        .filter({ night, noOfRuns -> noOfRuns > 2 })
        .penalize("only 2 VM runs per night", HardSoftScore.ONE_HARD,  { night, noOfRuns -> noOfRuns - 2 })
Reply all
Reply to author
Forward
0 new messages