Legacy Utility Theory

Theory

Utility Theory can be useful when selecting the best one of multiple available options.

In the context of hfsm.dev, it can be used to pick the 'best' sub-state when its region is activated via transition.

Two variants are supported: Maximum Score and Ranked Weighted Random.

Maximum Score

The 'best' sub-state is determined by the utility score, the option with the highest one is chosen.

Ranked Weighted Random

This method is described in Kevin Dill - Dual-Utility Reasoning (Game AI Pro 2, 2015).

In short, the 'best' sub-state is chosen between highest-ranking options, with probability proportional to its expected utility score.

Recommended Reading

• Von Neumann–Morgenstern utility theorem
• Kevin Dill, Dave Mark - Improving AI Decision Modeling Through Utility Theory (GDC 2010)
• Kevin Dill, Dave Mark - Embracing the Dark Art of Mathematical Modeling in AI (GDC 2012)
• David “Rez” Graham - An Introduction to Utility Theory (Game AI Pro, 2013)
• and others

Design

In addition to the conventional FSM direct transitions, hfsm.dev supports selector logic when transitioning into regions.

When a transition is made into a region rather than into one of its sub-states, one sub-state will be chosen to be activated, depending on the region type.

(The full list of available region types is available here).

API Summary

Type	Maximum Score	Ranked Weighted Random
Transitions	Control::utilize<TState>() Control::utilize(StateID)	Control::randomize<TState>() Control::randomize(StateID)
Roots	M::UtilitatianRoot<THead, TSubStates M::UtilitarianPeerRoot<TSubStates>	M::RandomRoot<THead, TSubStates M::RandomPeerRoot<TSubStates>
Regions	M::Utilitatian<THead, TSubStates M::UtilitarianPeers<TSubStates>	M::Random<THead, TSubStates M::RandomPeers<TSubStates>
State Methods	State::utility()	State::rank() State::utility()
Configuration	Config ::UtilityT<UtilityType>	Config ::RankT<TRank> ::UtilityT<TUtility> ::RandomT<TGenerator>

Triggers

Maximum Score:

• utilize<>() into any region
• changeTo<>() into M::Utilitarian<> or M::UtilitarianPeers<> regions
• initial activation of M::UtilitarianRoot<> or M::UtilitarianPeerRoot<> roots

Ranked Weighted Random:

• randomize<>() into any region
• changeTo<>() into M::Random<> or M::RandomPeers<> regions
• initial activation of M::RandomRoot<> or M::RandomPeerRoot<> roots

Selection Process

Maximum Score:

1. for every sub-state of the region being activated, call State::utility()
2. select the sub-state with the highest utilty score

Ranked Weighted Random:

1. for every sub-state of the region being activated, call State::rank()
2. filter out all sub-states with lower-than-highest rank
3. for all sub-states with the highest rank returned call State::utility()
4. select the sub-state using weighted-random logic based on their scores

Rank Calculation

State::rank() is queried only for the immediate sub-states of the region being activated.

Utility Score Calculation

Throughout hierarchy, State::utility() is queried recursively, for every sub-state of the region being activated, all the way to the last leaf states.

For all variations of composite sub-regions (including M::Composite<>, M::Resumable<>, M::Utilitarian<> and M::Random<>):

region_Utility == head_Utility * regionSubState_Utility;

For M::Orthogonal<> sub-region:

region_Utility == head_Utility * (regionSubState0_Utility + regionSubState1_Utility + ..) / regionSubStateCount;

The sub-state selection for the sub-states follows the rules defined for specific sub-region types.

Example

Shortened for readability, complete code snippet available in wiki_utility-theory.cpp.

#define HFSM_ENABLE_LOG_INTERFACE      // for hfsm2::LoggerInterface
#define HFSM_ENABLE_VERBOSE_DEBUG_LOG  // log inherited state methods
#include <hfsm2/machine.hpp>

struct Event {
    enum Enum {
        RANK,
        UTILITY,
        UTILITY_RESOLUTION,
        RANDOM_RESOLUTION,
    };

    // ..

    hfsm2::StateID state;
    Enum type;
    hfsm2::StateID prong;
};

struct Logger
    : hfsm2::LoggerInterface  // requires HFSM_ENABLE_LOG_INTERFACE defined
{
    // ..
};

using M = hfsm2::Machine;

using FSM = M::PeerRoot<
                struct Origin,
                M::Utilitarian<struct Destination,
                    struct S,
                    M::Composite<struct C,
                        struct C_Initial,
                        struct C_1
                    >,
                    M::Resumable<struct R,
                        struct R_0,
                        struct R_Activated
                    >,
                    M::Utilitarian<struct U,
                        struct U_033,
                        struct U_067
                    >,
                    M::Random<struct D,
                        struct D_Filtered,
                        struct D_010,
                        struct D_090
                    >,
                    M::Orthogonal<struct O,
                        struct O_0,
                        struct O_1
                    >
                >
            >;

struct Origin       : FSM::State {};

struct Destination  : FSM::State {};
struct S            : FSM::State {};

struct C            : FSM::State {};  // for 'Composite' region,
struct C_Initial    : FSM::State {};  // only consider the initial sub-state
struct C_1          : FSM::State {};

struct R            : FSM::State {};  // for 'Resumable' region,
struct R_0          : FSM::State {};
struct R_Activated  : FSM::State {};  // only consider previously activated sub-state

struct U            : FSM::State {};  // for 'Utilitarian' region,
                                      // find the highest-scoring sub-state
struct U_033        : FSM::State {
    Utility utility(const Control&) { return 0.33f; }
};

struct U_067        : FSM::State {
    Utility utility(const Control&) { return 0.67f; }
};

struct D            : FSM::State {};  // for 'Random' region,
                                      // 1. filter out low-ranking sub-states
                                      // 2. from the remaining sub-states,
                                      // randomly select one based on their score
struct D_Filtered   : FSM::State {
    Rank rank(const Control&) {return -1; }
};

struct D_010        : FSM::State {
    Rank rank(const Control&) {return 0; }
    Utility utility(const Control&) { return 0.10f; }
};

struct D_090        : FSM::State {
    // inherit FSM::State::rank(), which returns '0'
    Utility utility(const Control&) { return 0.90f; }
};

struct O            : FSM::State {};
struct O_0          : FSM::State {};
struct O_1          : FSM::State {};

void test() {
    Logger logger;
    FSM::Instance fsm{&logger};
    assert(fsm.isActive<Origin>());        // Initial activation

    fsm.changeTo<R_Activated>();
    fsm.update();
    assert(fsm.isActive<R_Activated>());   // Prepare resumable state

    fsm.changeTo<Origin>();
    fsm.update();
    assert(fsm.isActive<Origin>());        // Ready for the main test

    fsm.changeTo<Destination>();
    fsm.update();
    assert(fsm.isActive<Destination>());
    assert(fsm.isActive<S>());

    const Events reference = {
        { FSM::stateId<S>(),            Event::UTILITY },

        { FSM::stateId<C>(),            Event::UTILITY },
        { FSM::stateId<C_Initial>(),    Event::UTILITY },

        { FSM::stateId<R>(),            Event::UTILITY },
        { FSM::stateId<R_Activated>(),  Event::UTILITY },

        { FSM::stateId<U>(),            Event::UTILITY },
        { FSM::stateId<U_033>(),        Event::UTILITY },
        { FSM::stateId<U_067>(),        Event::UTILITY },
        { FSM::stateId<U>(),            Event::UTILITY_RESOLUTION, 1 }, // 'U_067' selected

        { FSM::stateId<D>(),            Event::UTILITY },
        { FSM::stateId<D_Filtered>(),   Event::RANK }, // will be filtered out, score not checked
        { FSM::stateId<D_010>(),        Event::RANK },
        { FSM::stateId<D_090>(),        Event::RANK },

        { FSM::stateId<D_010>(),        Event::UTILITY },
        { FSM::stateId<D_090>(),        Event::UTILITY },
        { FSM::stateId<D>(),            Event::RANDOM_RESOLUTION, 2 }, // 'D_090' selected

        { FSM::stateId<O>(),            Event::UTILITY },
        { FSM::stateId<O_0>(),          Event::UTILITY },
        { FSM::stateId<O_1>(),          Event::UTILITY },
        { FSM::stateId<O>(),            Event::UTILITY_RESOLUTION },

        { FSM::stateId<Destination>(),  Event::UTILITY_RESOLUTION, 0 }, // 'S' selected
    };
    logger.assertSequence(reference);
}

See Also

snippets/wiki_utility-theory.cpp
test/test_utility_regions.cpp
test/test_utilize.cpp