Portability	ghc
Stability	experimental
Maintainer	nickolay.kudasov@gmail.com
Safe Haskell	None

Control.Agent.Free.Algorithms.ABT

Contents

Algorithms
ABT Kernel API
Used data structures

Description

Family of ABT algorithms. Based on «The Asynchronous Backtracking Family» http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.4716.

Synopsis

Documentation

module Control.Agent.Free.Interfaces.SendRecv

Algorithms

type A i v a = forall m. Monad m => StateT (AgentState i v) (Agent' (ABTKernelF i v) m) a

A useful alias for a monad in which ABT algorithms run.

abtKernel :: (Ord i, Eq v) => A i v (Maybe v)

ABT Kernel algorithm.

ABT Kernel API

type ABTKernelF i v = SendRecv i (Message i v)

Abstract interface used by ABT Kernel algorithm.

sendOk :: MonadFree (ABTKernelF i v) m => i -> v -> m ()

Send OK? message. Requires address of another agent and a chosen value.

sendBacktrack :: MonadFree (ABTKernelF i v) m => i -> NoGood i v -> m ()

Send BACKTRACK message. Requires address of another agent and resolved nogood store.

sendStop :: MonadFree (ABTKernelF i v) m => i -> m ()

Send STOP message to the *system*. All agents in the system will receive this message.

Used data structures

newtype Constraint i v

A general constraint. Constraint i v is agent-oriented and is just a wrapper for the function of type AgentView i v -> v -> Maybe (NoGood i v). The latter checks whether constraint would hold given agent's view and a value it's going to choose. If constraint wouldn't hold, the function returns Just ngd (it generates NoGood), otherwise it returns Nothing.

Constructors

Constraint
Fields constraintCheck :: AgentView i v -> v -> Maybe (NoGood i v)

data Message i v

ABT Kernel messages.

Constructors

MsgOk v	OK? message is sent to higher agents so they could check it.
MsgBacktrack (NoGood i v)	BACKTRACK message is sent to lower agent to force it rechoose its value.
MsgStop	STOP message is sent when it is know that a problem has no solution.

Instances

(Show i, Show v) => Show (Message i v)

data NoGood i v

NoGood is a witness of a previous conflict. It is of the form x_i1 = v1 && ... && x_iN = vN => x_j /= v, where x_j refers to the agent holding this nogood in its nogood store.

Constructors

NoGood
Fields ngdLHS :: Map i v Left hand side of a nogood. ngdRHS :: (i, v) Right hand side of a nogood.

Instances

(Show i, Show v) => Show (NoGood i v)

type AgentView i v = Map i v

Agent view is just a Map from agents' adresses to agents' values.

data AgentState i v

State of an agent for ABT Kernel algorithm.

Constructors

AgentState

Fields

agStop :: Bool: Flag informing whether algorithm should stop.
agValue :: Maybe v: Currently chosen value.
agDomain :: [v]: Domain of agent's value.
agId :: i: ID (address) of an agent.
agView :: AgentView i v: Current agent's view.
agAbove :: [i]: IDs of higher agents.
agBelow :: [i]: IDs of lower agents.
agConstraints :: [Constraint i v]: Constraints involving an agent.
agNoGoods :: [NoGood i v]: Agent's nogood store.

initialAgentState :: AgentState i v

Initial agent's state.