|
AIToolbox
A library that offers tools for AI problem solving.
|
This class represents the Variable Elimination algorithm. More...
#include <AIToolbox/Factored/Bandit/Algorithms/Utils/VariableElimination.hpp>
Public Types | |
| using | Result = std::tuple< Action, double > |
| using | Factor = std::pair< double, std::vector< std::pair< size_t, size_t > >> |
| using | GVE = GenericVariableElimination< Factor > |
| using | Graph = GVE::Graph |
Public Member Functions | |
| Result | operator() (const Action &A, Graph &graph) |
| This function performs the actual agent elimination process. More... | |
This class represents the Variable Elimination algorithm.
This class performs variable elimination on a factor graph. It first builds the graph starting from a list of QFunctionRules. These rules are sorted by the agents they affect, and each group is added to a single factor connected to those agents.
Each agent is then eliminated from the graph, and all rules connected to it are processed in order to find out which action the agent being eliminated should take.
When all agents have been eliminated, only the optimal rules containing the best actions remain. The ones that provide the best reward are joined into a single Action, which is then returned.
This process is exponential in the maximum number of agents found attached to the same factor (which could be higher than in the original graph, as the elimination process can create bigger factors than the initial ones). However, given that each factor is usually linked to few agents, and that this process allows avoiding considering the full factored Action at any one time, it is usually much faster than a brute-force approach.
WARNING: This process only considers rules that have been explicitly passed to it. This may create problems if some of your values have negative values in it, since the elimination process will not consider unmentioned actions as giving 0 reward, and choose them instead of the negative values. In order to avoid this problem either all 0 rules have to be explicitly mentioned for each agent subgroup containing negative rules, or the rules have to be converted to an equivalent graph with positive values.
| using AIToolbox::Factored::Bandit::VariableElimination::Factor = std::pair<double, std::vector<std::pair<size_t, size_t> >> |
| using AIToolbox::Factored::Bandit::VariableElimination::Result = std::tuple<Action, double> |
| Result AIToolbox::Factored::Bandit::VariableElimination::operator() | ( | const Action & | A, |
| Graph & | graph | ||
| ) |
This function performs the actual agent elimination process.
For each agent, its adjacent factors, and the agents adjacent to those are found. Then all possible action combinations between those other agents are tried in order to find the best action response be for the agent to be eliminated.
All the best responses found are added as Rules to a (possibly new) factor adjacent to the adjacent agents.
The process is repeated until all agents are eliminated.
What remains is then joined into a single Action, containing the best possible value.
| A | The action space of the agents. |
| graph | The graph to perform VE on. |