AIToolbox::Factored::CPSQueue Class Reference

This class is used as the priority queue for CooperativePrioritizedSweeping. More...

#include <AIToolbox/Factored/MDP/Algorithms/Utils/CPSQueue.hpp>

Public Member Functions
	CPSQueue (const DDNGraph &graph)
	Basic constructor. More...
void	update (size_t i, size_t a, size_t s, double p)
	This function updates the probability of the input parent set. More...
void	reconstruct (State &s, Action &a)
	This function sets the input State and Action with the highest priority combination. More...
double	getNodeMaxPriority (size_t i) const
	This function returns the priority of the highest parent set of the selected node. More...
unsigned	getNonZeroPriorities () const
	This function returns how many non-zero priority parent sets there are. More...

Detailed Description

This class is used as the priority queue for CooperativePrioritizedSweeping.

This class performs a similar work as that done by Tries, but in a much more constrained way, so that it can be as fast as possible.

This class assumes keys are always the parent sets of some variable as represented in a DDN.

When doing the reconstruction, we select a single rule from each node, since all nodes's parents are by definition incompatible with each other. We always the best possible rule, and then randomly iterate over nodes, either picking their best possible rule if compatible or the best available alternative after picking a random local action.

Constructor & Destructor Documentation

CPSQueue()

AIToolbox::Factored::CPSQueue::CPSQueue

(

const DDNGraph &

graph

)

Basic constructor.

This constructor uses the inputs to construct the internal representation for priority rules, following the structure of the ddn.

Parameters

graph

The ddn of the transition function of the problem.

Member Function Documentation

getNodeMaxPriority()

double AIToolbox::Factored::CPSQueue::getNodeMaxPriority

(

size_t

i

)

const

This function returns the priority of the highest parent set of the selected node.

Parameters

i	The id of the selected node.

Returns

The priority of the highest parent set.

getNonZeroPriorities()

unsigned AIToolbox::Factored::CPSQueue::getNonZeroPriorities

(

)

const

This function returns how many non-zero priority parent sets there are.

The result is pre-computed during updates and reconstructions, so calling this function is always fast.

Returns

The number of current non-zero priority rules.

reconstruct()

void AIToolbox::Factored::CPSQueue::reconstruct	(	State &	s,
		Action &	a
	)

This function sets the input State and Action with the highest priority combination.

The highest priority parent set is always picked. Then, we randomly iterate over nodes, either picking their best possible rule if compatible or the best available alternative after picking a random local action.

This is the best we can do, as picking the true highest combination is NP-hard, and we want this to be as fast as possible so we can do many batch updates in CooperativePrioritizedSweeping.

Note that some elements may not be picked. These will be left with the value of the size of their respective space (so you can find them and decide what to do with them).

Parameters

s	The State to output, preallocated.
a	The Action to output, preallocated.

Returns

A set of Entry that match the input and each other, the Factors obtained by combining the input with the returned set.

update()

void AIToolbox::Factored::CPSQueue::update	(	size_t	i,
		size_t	a,
		size_t	s,
		double	p
	)

This function updates the probability of the input parent set.

This function takes ids directly to avoid having to pass through the toIndexPartial() function.

It increases the priority of the rule by 'p', and if necessary updates the maxes for the associated action/node so they can be more easily found later.

Parameters

i	The id of the node.
a	The id of the local joint action.
s	The id of the local parent states.
p	The priority to add.

---

The documentation for this class was generated from the following file:

• include/AIToolbox/Factored/MDP/Algorithms/Utils/CPSQueue.hpp