[rules-dev] Planner: Unified selectors

Hi guys, In Planner, I am going to do some structural improvements on the selectors. Below are some of the idea's on how to do that. All of these are ideas are still very volatile. Feed-back is welcome, especially if you don't like a particular naming or semantic. Global design objectives: - 1) Make selectors and generic MoveFactories faster, scalable and use less memory: by optionally not generating all the moves - 2) Make selectors and generic MoveFactories more configurable: filter on entities, variables, moveFilter, ... - 3) Unify entity, variable and value selectors under the same system, to also make them faster, scalable, memory-efficient and more configurable Let's focus on 1) MoveSelector only for now, on terminology and semantics. What does a MoveSelector need to have? Terminology of methods/attributes on MoveSelector. How would you name them? * Iterator<Move> moveIterator: o iterates over all the moves in the selector, based on the configuration of the MoveSelector * long moveSizeor size: o how many moves in this MoveSelector. o The MoveSelector interface probably doesn't need to expose this * boolean continuous: o Some value ranges, for example double x with (1.0 < x < 2.0) are continuous. + For example, a value can be 1.23435455444. o When true, then MoveSelector.size returns -1 or throws exception (because it is infinity really :) o Not all features will be able to combine with continuous true. + If it's not compatible, it fails-fast during configuration. * boolean cacheableBetweenSteps * enum orderType: o The order in which the moveIterator generates Moves o DEFAULT (or FROM_SOLUTION?) + not cached # The Moves are generated in real-time (at each move scope) * A1, A2, A3, ... A9, B1, B2, ... F9 + 100% cached # The Moves are generated in advance (at each step scope) and iterated in generated order. * A1, A2, A3, ... A9, B1, B2, ... F9 + Not compatible with continuous == true o DECREASING_DIFFICULTY (experimental) + B1, B2, … B9, F1, F2, … F9, A1, A2 …, C9 + This is really DEFAULT for the MoveSelector with DECREASING_DIFFICULTY for the entitySelector and DEFAULT/DECREASING_STRENGTH/... for the valueSelector o RANDOM_COMPLETE + The Moves are generated in advanced (at each step scope) and shuffled, so iterated in random order. # C2, B2, A7, E4, F3 ... + Not compatible with continuous == true o RANDOM_SCALABLE + The moves are generated in real-time (at each move scope) randomly. # C2, B2, A7, E4, C2 ... + Will sometimes generate the same Move twice, before some other Move is generated once. * boolean hasFiniteMoveSize o Other names: + hasFiniteAmountOfMoves + knowsWhenAllMovesHaveBeenIterated o true if moveIterator.hasNext() will ever return false o It's false in the following cases: + orderType == RANDOM_SCALABLE * boolean roundRobinSelection o true if it should try to round robin selection between steps o If orderType == IN_ORDER + Suppose the moves are (A1, A2, A3, A4, A5) + if the first step stops after 3 move selections, it gets [A1, A2, A3] + then the next step will get [A4, A5, A1, A2, A3]. # so if it stops after the 3 move selections, it gets [A4, A5, A1] * with roundRobinSelection == false it would get [A1, A2, A3] again o If orderType == RANDOM_COMPLETE + This is a bit tricker - ignore for now o Not compatible with orderType == RANDOM_SCALABLE o Not compatible with continuous == true * long randomSelectionWeight o If this MoveSelector is put into a composition with another MoveSelector, how high is the chance that this MoveSelector is chosen? o See below on composition for more info. o Can default to 1 or can default to size. + Currently, Planner 5.4 implementation default it to 1. MoveSelector composition: Local Search can only have 1 direct MoveSelector, but that one can be CompositeMoveSelector of other MoveSelectors. There are several forms of composition: * Summed composition: UNION: o If X(A1, A2, A3) and Y(B1, B2) are summed, we get (A1, A2, A3, B1, B2) o If this composition is called with RANDOM (complete or scalable), how high is the change that A1 will be selected? + if randomSelectionWeight = 1 for each, so on X = 1 and Y = 1: # (1/2) * (1/3) = 1/6 chance to select A1 + if randomSelectionWeight = size for each, so on X = 3 and Y = 2: # 1/(3 + 2) = 1/5 chance to select A1 + Think about it: currently randomSelectionWeight = 1, # so if you have 100 change moves and 1000 swap moves, # then every change move has 10 times more chance to be selected then a swap move * Multiplied composition: CARTESIAN_PRODUCT: o If X(A1, A2, A3) and Y(B1, B2) are multiplied, we get (A1-B1, A1-B2, A2-B1, A2-B2, A3-B1, A3-B2) + So you get composite moves: even though X and Y only move 1 entity, the composite move moves 2 at the same time # If multiplied composition is useful is yet to be determined o If this composition is called with RANDOM (complete or scalable), how high is the change that A1-B1 will be selected? + Always (1/3) * (1/2) = 1/6 chance to select A1-B1 + The randomSelectionWeight doesn't matter! * if randomSelectionWeight = 1 , so on X = 1 and Y = 1: * (1/3) * (1/2) = 1/6 chance to select A1-B1 * if randomSelectionWeight = size, so on X = 3 and Y = 2: * (1/3) * (1/2) = 1/6 chance to select A1-B1 I hope this makes sense :) What do you think? Naming, semantics, usage, ... MoveFilters, entity inclusion/exclusion, etc are for phase 2 (by much easier to do once this stuff in in place) -- With kind regards, Geoffrey De Smet