Decision Making - PROCEED-Labs/proceed GitHub Wiki

In the PROCEED Engine there is one Decider component containing a Router that determines to which Engine sent the next upcoming task. The decision is based on different constraints.

The routing process involves multiple stages in which machines are filtered, until the router is left with a set of nodes which are all considered optimal.

There are hard and soft constraints (also called requirements). A machine is considered optimal if it satisfies all hard constraints, and achieves the highest (weighted) score based on soft constraints.

The evaluated attribute of a constraint, e.g. the available memory, can be both -- a hard and soft constraints. For example, saying that the available memory needs to be over a specific value is a hard constraint, but saying that the engine with the most available free memory should be taken is a soft constraint.

In the following sections we first give an overview about example use cases and then we define the structure of hard and soft constraints.

There are four places a constraints can be valid for:

• Next Flow Node: usually the requirements for the next activity
• Process: requirements concerning the complete process
• Process Participant: constraints concerning and coming from the process worker/user of a process
• Environment: constraints set by the machine owner

see here: https://docs.proceed-labs.org/concepts/bpmn/bpmn-constraints/#currently-supported-constraints

Use-Cases for Hard Constraints include, but are not limited to:

• Restricting the execution of an activity to a specific user, network, device
• Defining minima or maxima of machine attributes, like:
  • CPU Cores
  • Avg. CPU Load
  • RAM
  • Disk Space
• Calculate the distance and time to travel from one machine to other geographic locations, using an API like Google Maps

Hard constraint are Boolean expressions which can be used to define requirements that must be satisfied by a machine in order to be potentially optimal.

attribute-operand constraint-operator constraint-operand

• attribute (aka "Name") defines to which attribute the constraint is applied on, e.g. CPU
• constraint-operator (aka "Condition") defines how the attribute-operand is constraint e.g. <, >, ==.
• constraint-operand (aka "Value") is the requirement the attribute operand needs to adhere, e.g. 4

Complete example: CPU > 4

In the PROCEED Engine, the underlying value of the attribute can be resolved by the data about machines returned from the machine module. See machine information.

Constraints are represented inside the BPMN XML within an extension element either as part of the complete process or as part of one flow element. See BPMN constraints.

All single constraint definitions are AND connections, i.e. every given constraint must be fulfilled. If the constraint value contains an Array, it is an OR connection, i.e. only one value must be fulfilled.

attribute-operand is type-checked upon evaluation. If the underlying value is a function, it will be executed. The result will be substituted with the existing attribute-operand before the whole Boolean expression is evaluated. This is useful if the value must be dynamically calculated upon evaluation e.g. measuring the time it would take to travel from the machine to a geographic location defined in the activity.

Hard constraints support all comparison operators available in JavaScript. See comparison operators and logical operators. However some of these operators might not be useful in the context of hard constraints.

See router.test.js for more test cases.

it('should return true if constraint is satisfied', () => {
    // Instantiate Hard Constraint.
    const c = new HardConstraint('available_memory >= 1024');

    // Machine data fetched with discovery/network module.
    const machine = { available_memory: 1025 };

    // Evaluate the constraint against a machine.
    expect(c.satisfiedByMachine(machine)).toBe(true);
});

it('should support functions as attribute operands', () => {
    const c = new HardConstraint('funcThatReturnsFourtyTwo === 42');

    // Functions that are defined on the activity will be mapped to
    // the machine object and executed in its context.
    const machine = {
        funcThatReturnsFourtyTwo: () => 42,
    };

    expect(c.satisfiedByMachine(machine)).toBe(true);
});

In this example a custom constraint operator was defined. The unary operator, meaning it only accepts one operand, verifies that the machine supports a capability.

it('should support unary operators', () => {
    const c = new HardConstraint('capability_exists take-photo');
    expect(c.operator).toBe('capability_exists');
});

Soft constraints can be used to define the direction in which to optimize an attribute. Therefore the only two options are maximization and minimization (max and min).

Due to the fact that the PROCEED engine is including, but not limited to IOT devices, which are often Microcontrollers, running on very limited resources, only very resource-efficient optimization algorithms can be considered. The current implementation of the router optimizes a problem using a score-based approach.

In a score-based optimization the machines attributes are united in a single score function which is then maximized. To make the different units of the attributes comparable, the score function uses the relative values of the attributes. Preferences towards specific attributes can be expressed by prepending weights to the relative values.

It is possible for multiple machines to achieve the same score, even if the attributes are different. This is logically correct and means that both machines balance out their disadvantages with plenty of other resources. To decrease the likelihood of these cases it is recommend to define both maxima and minima as hard constraints against each attribute.

For the understanding of the implementation it important to know that there is a small difference between the User view (as the constraint developer) and the Decider view on the Constraint Data.

The Network Component collects every information of the other Engines. But some data is stored multiple times on the Engine, e.g. it is possible that there are multiple User Profiles on an Engine. This data is represented as multiple objects inside an array in the Network Component Representation of an Engine. This can be true for the following objects: user, user.role, machine.network, machine.display

The user (as the constraint developer) on the other hand does not need to know the technical details of the internal data structure. The only thing he wants to say is: The next task should be operated by the user max, so he only uses user.name == 'max' to specify the rule.

It is the task of the decider to abstract this technical mismatch away.