NAME
Schedule::Activity - Generate random activity schedules
VERSION
Version 0.1.9
SYNOPSIS
use Schedule::Activity;
my $scheduler=Schedule::Activity->new(
configuration=>{
node=>{
Activity=>{
message=>'Begin Activity',
next=>['action 1'],
tmmin=>5,tmavg=>5,tmmax=>5,
finish=>'Activity, conclude',
},
'action 1'=>{
message=>'Begin action 1',
tmmin=>5,tmavg=>10,tmmax=>15,
next=>['action 2'],
},
'action 2'=>{
message=>'Begin action 2',
tmmin=>5,tmavg=>10,tmmax=>15,
next=>['Activity, conclude'],
},
'Activity, conclude'=>{
message=>'Conclude Activity',
tmmin=>5,tmavg=>5,tmmax=>5,
},
},
annotations=>{...},
attributes =>{...},
messages =>{...},
}
);
my %schedule=$scheduler->schedule(activities=>[
[30,'Activity'],
...
]);
if($schedule{error}) { die join("\n",@{$schedule{error}}) }
print join("\n",map {"$$_[0]: $$_[1]{message}"} @{$schedule{activities}});DESCRIPTION
This module permits building schedules of activities each containing randomly-generated lists of actions. This two-level approach uses explicit goal times to construct the specified list of activities. Within activities, actions are chosen within configured limits, possibly with randomization and cycling, using slack and buffer timing adjustments to achieve the goal.
For additional examples, see the samples/ directory.
Areas subject to change are documented below. Configurations and goals may lead to cases that currently die(), so callers should plan to trap and handle these exceptions accordingly.
Note: The static method Schedule::Activity::buildSchedule will be removed in version 0.2.0.
CONFIGURATION
A configuration for scheduling contains the following sections:
%configuration=(
node =>{...}
attributes =>... # see below
annotations=>... # see below
messages =>... # see below
)Both activities and actions are configured as named node entries. With this structure, an action and activity may have the same message, but must use different key names.
'activity name'=>{
message=>... # an optional message string or object
next =>[...], # list of child node names
finish =>'activity conclusion',
#
(time specification)
(attributes specification)
}
'action name'=>{
message=>... # an optional message string or object
next =>[...], # list of child node names
#
(time specification)
(attributes specification)
}The list of next nodes is a list of names, which must be defined in the configuration. During schedule construction, entries will be chosen randomly from the list of next nodes. The conclusion must be reachable from the initial activity, or scheduling will fail. There is no further restriction on the items in next: Scheduling specifically supports cyclic/recursive actions, including self-cycles.
There is no functional difference between activities and actions except that a node must contain finish to be used for activity scheduling. Nomenclature is primarily to support schedule organization: A collection of random actions is used to build an activity; a sequence of activities is used to build a schedule.
Time specification
The only time specification currently supported is:
tmmin=>seconds, tmavg=>seconds, tmmax=>secondsValues must be non-negative numbers. All three values may be identical. Note that scheduling to a given goal may be impossible without slack or buffer within some of the actions:
slack =tmavg-tmmin
buffer=tmmax-tmavgThe slack is the amount of time that could be reduced in an action before it would need to be removed/replaced in the schedule. The buffer is the amount of time that could be added to an action before additional actions would be needed in the schedule.
Providing any time value will automatically set any missing values at the fixed ratios 3,4,5. EG, specifying only tmmax=40 will set tmmin=24 and tmavg=32. If provided two time values, priority is given to tmavg to set the third.
Scheduling may be controlled with the tension settings described below. Future changes may support automatic slack/buffering, univeral slack/buffer ratios, and open-ended/relaxed slack/buffering.
Messages
Each activity/action node may contain an optional message. Messages are provided so the caller can easily format the returned schedules. While message attributes may be used during schedule, the message strings themselves are not used during scheduling. Messages may be:
message=>'A message string'
message=>'named message key'
message=>['An array','of alternates','chosen randomly']
message=>{name=>'named message key'}
message=>{
alternates=>[
{message=>'A hash containing an array', attributes=>{...}}
{message=>'of alternates', attributes=>{...}}
{message=>'with optional attributes', attributes=>{...}}
{message=>'named message key'}
{name=>'named message key'}
]
}Message selection is randomized for arrays and a hash of alternates. Any attributes are emitted with the attribute response values, described below.
RESPONSE
The response from schedule(activities=[...])> is:
%schedule=(
error=>['list of validation errors, if any',...],
activities=>[
[seconds, message],
..,
],
annotations=>{
'group'=>{
events=>[
[seconds, message],
]
},
...
},
attributes=>{
name=>{
y =>(final value),
xy =>[[tm,value],...],
avg=>(average, depends on type),
},
...
},
)Failures
In addition to validation failures returned through error, the following may cause the scheduler to die(): The activity name is undefined. The scheduler was not able to reach the named finish node. The number of retries or backtracking attempts has been exhausted.
The difference between the result time and the goal may cause retries when an excess exceeds the available slack, or when a shortage exceeds the available buffer.
Caution: While startup/conclusion of activities may have fixed time specifications, at this time it is recommended that actions always contain some slack/buffer. There is currently no "relaxing mechanism" during scheduling, so a configured with no slack nor buffer must exactly meet the goal time requested.
SCHEDULING ALGORITHM
The configuration of the next actions is the primary contributor to the schedules that can be built. As with all algorithms of this type, there are many configurations that simply won't work well: For example, this is not a maze solver, a best path finder, nor a resourcing optimization system. Scheduling success toward the stated goals generally requires that actions have different tmmin, tmmax, and tmavg, and that actions permit reasonable repetition and recursion. Highly imbalanced actions, such as a branch of length 10 and another of length 5000, may always fail depending on the goal. Neverthless, for the activities and actions so described, how does it work?
The scheduler is a randomized, opportunistic, single-step path growth algorithm. An activity starts at the indicated node. At each step, the next entries are filtered and a random action is chosen, then the process repeats. The selection of the next step is restricted based on the current time (at the end of the action) as follows.
First, a random current time is computed based on the current time, the accumulated slack and buffer, and the tension settings (see below). If the random current time is less than the goal time, the next action will be a random non-final node, if available, or the final node if all other choices are filtered or unavailable.
If the random current time is greater than the goal time and the final action is listed as a next action, it will be chosen.
In all other cases, a random next action will be chosen.
Tension
Schedule construction proceeds toward the goal time incrementally, with each action appending its tmavg until the goal is reached. If the accumulated average times were exactly equal to the goal for the activity, schedules would be unambiguous. For repeating, recursive scheduling, however, it's necessary to consider scenarios where the actions don't quite reach the goal or where they extend beyond the goal.
Buffer and Slack
Each activity node and action has buffer and slack, as defined above, that contributes to the accumulated total buffer and slack. The amount of buffer/slack that contributes to the random current time is controlled by including schedule(tensionbuffer=>value) and tensionslack=>value, each between 0 and 1. Tension effectively controls how little of each contributes toward randomization around the goal.
In the 'laziest' mode, with tension=0.0, all available buffer/slack is used to establish the random current time, increasing the likelihood that it is greater than the goal. With a lower buffer tension, for example, scheduling is more likely to reach the final activity node sooner, and thus will contain a smaller number of actions on average, each stretched toward tmmax. With a higher tension, the goal time must be met (or exceeded) before aggressively seeking the final activity node, so schedules will contain a larger number of actions, each compressed toward tmmin.
The tension for slack is similar, with lower values permitting a larger number of actions beyond the goal, each compressed toward tmmin, whereas with tension near 1, scheduling will seek the final activity node as soon as the schedule time exceeds the goal, resulting in a smaller number of activities.
The random computed time is a uniform distribution around the current time, but because actions are scheduled incrementally, this leads to a skewed distribution that favors a smaller number of actions. See samples/tension.png for the distributions where exactly 100 repeated actions would be expected.
The default values are 0.5 for the slack tension, and ~0.85 for the buffer tension. This gives an expected number of actions that is very close to goal/tmavg, roughly plus 10% minus 5%.
Response
The scheduling response contains {stat} that reports the accumulated slack and buffer used for all actions, as well as slackttl and bufferttl which represent the maximum available. The amount of slack used during scheduling is slack/slackttl, and the same for buffer. These values can assist with choosing tension settings based on the specific configuration.
ATTRIBUTES
Attributes permit tracking boolean or numeric values during schedule construction. The result of schedule contains attribute information that can be used to verify or adjust the schedule.
Types
The two types of attributes are bool or int, which is the default. A boolean attribute is primarily used as a state flag. An integer attribute can be used both as a counter or gauge, either to track the number of occurrences of an activity or event, or to log varying numeric values.
Configuration
Multiple attributes can be referenced from any activity/action. For example:
'activity/action name'=>{
attributes=>{
temperature=>{set=>value, incr=>value, decr=>value, note=>'comment'},
counter =>{set=>value, incr=>value, note=>'comment'},
flag =>{set=>0/1, note=>'comment'},
},
}Any attribute may include a note for convenience, but this value is not stored nor reported.
The main configuration can also declare attribute names and starting values. It is recommended to set any non-zero initial values in this fashion, since calling set requires that activity to always be the first requested in the schedule. Boolean values must be declared in this section:
%configuration=(
attributes=>{
flagA =>{type=>'bool'},
flagB =>{type=>'bool', value=>1},
counter=>{type=>'int', value=>0},
},
)Attributes within message alternate configurations and named messages are identified during configuration validation. Together with activity/action configurations, attributes are verified before schedule construction, which will fail if an attribute name is referenced in a conflicting manner.
Response values
The response from schedule includes an attributes section as:
attributes=>{
name=>{
y =>(final value),
xy =>[[tm,value],...],
avg=>(average, depends on type),
},
...
}The y value is the last recorded value in the schedule. The xy contains an array of all values and the times at which they changed; see Logging. The avg is roughly the time-weighted average of the value, but this depends on the attribute type.
If an activity containing a unique attribute is not used during construction, the attribute will still be included in the response with its default and initial value.
Integer attributes
The int type is the default for attributes. If initialized in %configuration, it may specify the type, or the value, or both. The default value is zero, but this may be overwritten if the first activity node specifically calls set.
Integer attributes within activity/actions support all of: set, incr, decr. There is no actual restriction on type so any Perl number is valid, integers or real numbers, positive or negative.
The reported avg is the overall time-weighted average of the values, computed via a trapezoid rule. That is, if tm=0, value=2 and tm=10, value=12, the average is 7 with a weight of 10. See Logging for more details.
Boolean attributes
The bool type must be declared in %configuration. The value may be specified, but defaults to zero/false.
Boolean attributes within activity/actions support: set. Currently there is no restriction on values, but the behavior is only defined for values 0/1.
The reported avg is the percentage of time in the schedule for which the flag was true. That is, if tm=0, value=0, and tm=7, value=1, and tm=10, value=1 is the complete schedule, then the reported average for the boolean will be 0.3.
Precedence
When an activity/action node and a selected message both contain attributes, the value of the attribute is updated first from the action node and then from the message node. For boolean attributes, this means the "value set in the message has precedence". For integer attributes, suppose that the value is initially zero; then, if both the action and message have attribute operators, the result will be:
Action Message Value
set=1 set=2 2
incr=3 set=4 4
set=5 incr=6 11
incr=7 incr=8 15Logging
The reported xy is an array of values of the form (tm, value), with each representing an activity/action referencing that attribute built into the schedule. Each attribute will have its initial value of (0, value), either the default or the value specified in configuration{attributes}.
Any attribute may be "fixed" in the log at their current value with the configuration name=>{}, which is equivalent to incr=0 for integers.
Attribute logging always occurs at the beginning and end of the completed schedule, so that all scheduled time affects the weighted average value calculation. Activities may reset or fix attributes in their beginning or final node; the final node is only the "end of the activity" when tmavg=0.
ANNOTATIONS
A scheduling configuration may contain a list of annotations:
%configuration=(
annotations=>{
'annotation group'=>[
{annotation configuration},
...
]
},
)Scheduling annotations are a collection of secondary events to be attached to the built schedule and are configured as described in Schedule::Activity::Annotation. Each named group can have one or more annotation. Each annotation will be inserted around the matching actions in the schedule and be reported from schedule in the annotations section as:
annotations=>{
'group'=>{
events=>[
[seconds, message],
...
]
},
}Within an individual group, earlier annotations take priority if two events are scheduled at the same time. Multiple groups of annotations may have conflicting event schedules with event overlap. Note that the between setting is only enforced for each annotation individually at this time.
Annotations do not update the attributes response from schedule. Because annotations may themselves contain attributes, they are retained separately from the main schedule of activities to permit easier rebuilding. At this time, however, the caller must verify that annotation schedules before merging them and their attributes into the schedule. Annotations may also be built separately after schedule construction as described in Schedule::Activity::Annotation.
Annotations may use named messages, and messages in the annotations response structure are materialized using the named message configuration passed to schedule.
NAMED MESSAGES
A scheduling configuration may contain a list of common messages. This is particularly useful when there are a large number of common alternate messages where copy/pasting through the scheduling configuration would be egregious.
%configuration=(
messages=>{
'key name'=>{ any regular message configuration }
...
},
)Any message configuration within activity/action nodes may then reference the message by its key as shown above. During message selection, any string message or configured name will return the message configuration for key=name, if it exists, or will return the string message. If a configured message string matches a referenced name, the name takes precedence.
The configuration of a named message may only create string, array, or hash alternative messages; it cannot reference another name.
This feature is experimental starting with version 0.1.2.
FILTERING
Experimental starting with version 0.1.6.
Action nodes may include prerequisites before they will be selected during scheduling:
'action name'=>{
require=>{
...
}
...
}During schedule construction, the list of next actions will be filtered by require to identify candidate actions. The current attribute values at the time of selection will be used to perform the evaluation. The available filtering criteria are fully described in Schedule::Activity::NodeFilter and include attribute numeric comparison and Boolean operators.
Action filtering may be used, together with attribute setting and increments, to prevent certain actions from appearing if others have not previously occurred, or vice versa. This mechanism may also be used to specify global or per-activity limits on certain actions.
Slack and Buffer
During scheduling, filtering is evaluated as a single pass only, per activity: When finding a sequence of actions to fulfill a scheduling goal for an activity, candidates (from next) are checked based on the current attributes. Action times during construction are based on tmavg, so any filter using attribute average values will be computed as if the action sequence only used tmavg. After a solution is found, however, actions are adjusted across the total slack/buffer available, so the "materialized average" attribute values can be slightly different.
This should never affect attributes used for a stateful/flag/counter-based filter, because those value changes will still occur in the same sequence.
IMPORT MECHANISMS
Markdown
Rudimentary markdown support is included for lists of actions that are all equally likely for a given activity:
* Activity One, 5min
- Action one, 1min
- Action two, 2min
- Action three, 3min
2. Activity Two, 5min
* Action one, 1min
* Action two, 2min
* Action three, 3min
- Activity Three, 5min
* Action one, 5minAny list identification markers may be used interchangably (number plus period, asterisks, hyphen). One or more leading whitespace (tabs or spaces) indicates an action; otherwise the line indicates an activity. Times are specified as \d+min or \d+sec. If only a single action is included in an activity, its configured time should be equal to the activity time.
The imported configuration permits an activity to be followed by any of its actions, and any action can be followed by any other action within the activity (but not itself). Any action can terminate the activity.
The full settings needed to build a schedule can be loaded with %settings=loadMarkdown(text), and both $settings{configuration} and $settings{activities} will be defined so an immediate call to schedule(%settings) can be made.
BUGS
It is possible for some settings to get stuck in an infinite loop: Be cautious setting tmavg=0 for actions.
(This should be fixed in 0.1.7). There is currently a limitation with scheduling to the maximum buffer that is dependent on the behavior that a list of next actions with only a single entry will return that entry (even if it would have been otherwise filtered). The exceptions need to be updated so that the maximum buffer includes the tmmax of the conclusion node itself, otherwise the conclusion node will get filtered out and scheduling will fail.
SEE ALSO
Schedule::LongSteps and Chronic address the same type of schedules with slightly different goals.