[rules-dev] Planner: Unified selectors
Geoffrey De Smet
ge0ffrey.spam at gmail.com
Mon May 7 03:12:26 EDT 2012
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-dev/attachments/20120507/dabfd43d/attachment-0001.html
More information about the rules-dev
mailing list