search

package
v0.0.0-...-b76af60 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 23, 2021 License: MIT Imports: 19 Imported by: 0

Documentation

Overview

Copyright 2018/2019, University of Freiburg, Chair of Artificial Intelligence. Authors:

  • Robert Grönsfeld
  • Tim Schulte <schultet@informatik.uni-freiburg.de>.

Index

Constants

View Source 
const (
	MinInt32 = -1 << 31
)

Variables

This section is empty.

Functions

func DistanceToRoot 

func DistanceToRoot(n Node) int

DistanceToRoot computes how many actions away a node is from the root

func DotEdgeString 

func DotEdgeString(n1, n2 *DmtMakespanNode) string

func DotGraph 

func DotGraph(root *DmtMakespanNode, file string)

func DotNodeLabel 

func DotNodeLabel(n *DmtMakespanNode, m int) string

func DotNodeString 

func DotNodeString(n *DmtMakespanNode, m int) string

func DotPlan 

func DotPlan(goal *DmtMakespanNode, file string)

func RegisterStrategy 

func RegisterStrategy(info *StrategyInfo)

RegisterStrategy a new StrategyInfo object to the strategyRegistry. This step is required to select the underlying strategy from the command line.

func Satisfies 

func Satisfies(s state.State, cs task.ConditionSet) bool

Satisfies returns true iff the state satisfies all conditions in cs

func Successor 

func Successor(s state.State, o *task.Action) state.State

Successor computes the successor state that results from applying action o to state s. TODO: move somewhere more suitable (maybe mpt.StateRegistry

Types

type AStarQueue 

type AStarQueue struct {
	// contains filtered or unexported fields
}

Queue for A* search

func NewAStarQueue 

func NewAStarQueue() *AStarQueue

func (*AStarQueue) Get 

func (q *AStarQueue) Get(i int) ValueNode

Get returns node at index i (NodeGetter interface)

func (AStarQueue) Len 

func (q AStarQueue) Len() int

func (AStarQueue) Less 

func (q AStarQueue) Less(i, j int) bool

func (*AStarQueue) Pop 

func (q *AStarQueue) Pop() interface{}

Pop removes the first element from the queue

func (*AStarQueue) Push 

func (q *AStarQueue) Push(x interface{})

Push adds a new element to the queue

func (*AStarQueue) Put 

func (q *AStarQueue) Put(x interface{})

func (AStarQueue) Swap 

func (q AStarQueue) Swap(i, j int)

func (*AStarQueue) Take 

func (q *AStarQueue) Take() interface{}

type ActionEvaluator 

type ActionEvaluator interface {
	ApplicableActions(s state.State) task.ActionList
	ApplicableAgents(s state.State) []int
}

An ActionEvaluator can compute applicable actions

func NewActionEvaluator 

func NewActionEvaluator(vars []*task.Variable, am task.ActionMap, id int) ActionEvaluator

NewActionEvaluator creates and returns an appTester

func NewPruningEvaluator 

func NewPruningEvaluator(am ActionEvaluator, ap ActionPruner) ActionEvaluator

type ActionPruner 

type ActionPruner interface {
	Prune(*state.State, []*task.Action) []*task.Action
}

ActionPruner interface type to implement various pruning techniques (like stubborn sets) for pruning actions

type BackupQueue 

type BackupQueue struct {
	// contains filtered or unexported fields
}

BackupQueue implements a PQ for node backups ordered by depth in the tree

func NewBackupQueue 

func NewBackupQueue() *BackupQueue

NewBackupQueue returns a new DmtQueue

func (*BackupQueue) Clear 

func (q *BackupQueue) Clear()

clear resets and re-initializes a DmtQueue

func (BackupQueue) Len 

func (q BackupQueue) Len() int

Len returns the number of elements in the queue

func (BackupQueue) Less 

func (q BackupQueue) Less(i, j int) bool

TODO: comment

func (*BackupQueue) Pop 

func (q *BackupQueue) Pop() interface{}

Pop removes the first element from the queue

func (*BackupQueue) Push 

func (q *BackupQueue) Push(x interface{})

Push adds a new element to the queue

func (*BackupQueue) Put 

func (q *BackupQueue) Put(x interface{})

func (BackupQueue) Swap 

func (q BackupQueue) Swap(i, j int)

Swap swaps the position of the elements at the provided indices in the queue

func (*BackupQueue) Take 

func (q *BackupQueue) Take() interface{}

type ClosedList 

type ClosedList map[state.StateID]*MafsNode

ClosedList is a hashmap containing all nodes expanded during search

func (ClosedList) Add 

func (cl ClosedList) Add(n *MafsNode)

type Dmt 

type Dmt struct {
	*Engine
	// contains filtered or unexported fields
}

Dmt search, implements search.Strategy interface

func (*Dmt) HasNode 

func (d *Dmt) HasNode(sid state.StateID) (Node, bool)

HasNode returns the node stored with NodeID id in transmittedNodes and a truth value representing whether the id is in the table.

func (*Dmt) Initialize 

func (d *Dmt) Initialize()

Initialize initializes dmt search TODO: testing

func (*Dmt) Step 

func (d *Dmt) Step() Status

Step executes a single search step (is called repeatedly by search.Engine)

func (*Dmt) Tokens 

func (d *Dmt) Tokens(n Node) state.State

Tokens returns the tokenarray registered with node n.

type DmtMakespan 

type DmtMakespan struct {
	*Engine
	// contains filtered or unexported fields
}

DmtMakespan search, implements search.Strategy interface

func (*DmtMakespan) HasNode 

func (d *DmtMakespan) HasNode(sid state.StateID) (Node, bool)

HasNode returns the node stored with NodeID id in transmittedNodes and a truth value representing whether the id is in the table.

func (*DmtMakespan) Initialize 

func (d *DmtMakespan) Initialize()

Initialize initializes dmt search TODO: testing

func (*DmtMakespan) Step 

func (d *DmtMakespan) Step() Status

Step executes a single search step (is called repeatedly by search.Engine)

func (*DmtMakespan) Tokens 

func (d *DmtMakespan) Tokens(n Node) state.State

Tokens returns the tokenarray registered with node n.

type DmtMakespanNode 

type DmtMakespanNode struct {
	// contains filtered or unexported fields
}

DmtMakespanNode implements search.Node

func (*DmtMakespanNode) Action 

func (n *DmtMakespanNode) Action() *task.Action

Action returns the nodes creating action

func (*DmtMakespanNode) ID 

func (n *DmtMakespanNode) ID() state.StateID

ID returns the unique NodeID of the node

func (*DmtMakespanNode) Parent 

func (n *DmtMakespanNode) Parent() Node

Parent returns the nodes parent node

func (*DmtMakespanNode) String 

func (n *DmtMakespanNode) String() string

String returns a string representation of n

type DmtMessage 

type DmtMessage struct {
	SenderID int
	State    []int // SharedState
	Action   int
	G        int
	H        int
}

DmtMessage contains the search state and other information

type DmtNode 

type DmtNode struct {
	// contains filtered or unexported fields
}

DmtNode implements search.Node

func NewDmtNode 

func NewDmtNode(sid state.StateID, par *DmtNode, op *task.Action, cost, h, v int) *DmtNode

NewDmtNode creates a new DmtNode

func (*DmtNode) Action 

func (n *DmtNode) Action() *task.Action

Action returns the nodes creating action

func (*DmtNode) ID 

func (n *DmtNode) ID() state.StateID

ID returns the unique NodeID of the node

func (*DmtNode) Parent 

func (n *DmtNode) Parent() Node

Parent returns the nodes parent node

func (*DmtNode) String 

func (n *DmtNode) String() string

String returns a string representation of n

type Engine 

type Engine struct {
	Strategy
	*task.Task
	// contains filtered or unexported fields
}

Engine holds all the data structures needed for performing the actual search. It implements a high level Search algorithm, that repetitively calls the step() method of the Strategy object.

func NewEngine 

func NewEngine(t *task.Task, server comm.Server, dispatcher comm.Dispatcher,
	conns comm.ConnList, opts *opt.OptionSet) *Engine

NewEngine creates a new search engine.

func (*Engine) Search 

func (e *Engine) Search(searchTimeout time.Duration)

Search is the engine's main search routine, calling the implemented Strategy's step() function until status changes to solved, failed, or timeout

func (*Engine) SetComm 

func (e *Engine) SetComm(s comm.Server, d comm.Dispatcher)

SetComm sets the engine's communication server and dispatcher

func (*Engine) SetDispatcher 

func (e *Engine) SetDispatcher(d comm.Dispatcher)

SetDispatcher sets the engine's message dispatcher to d

func (*Engine) SetServer 

func (e *Engine) SetServer(s comm.Server)

SetServer sets the engine's server to s

func (*Engine) SetStrategy 

func (e *Engine) SetStrategy(s Strategy)

SetStrategy sets the engine's search strategy to s

func (*Engine) Tokens 

func (e *Engine) Tokens(n Node) []int

type FactPair 

type FactPair struct {
	Variable int
	Value    int
}

FactPair represents a variable value-assignment (its basically the same as task.VariableValuePair or task.Condition)

type Mafs 

type Mafs struct {
	*Engine
	// contains filtered or unexported fields
}

Mafs (Multi agent forward search) implements search.Strategy interface

func (*Mafs) HasNode 

func (bfs *Mafs) HasNode(sid state.StateID) (Node, bool)

HasNode returns the node associated with sid in closed list

func (*Mafs) Initialize 

func (bfs *Mafs) Initialize()

Initialize initializes Mafs search

func (*Mafs) NewNode 

func (bfs *Mafs) NewNode(sid state.StateID, par *MafsNode, a *task.Action, g, h int) *MafsNode

NewNode returns a new MafsNode

func (*Mafs) Step 

func (bfs *Mafs) Step() Status

Step removes and expands best node from open list and adds it to closed list. Returns idle when open list is empty, solved when a goal is found, and inProgress otherwise.

func (*Mafs) Tokens 

func (bfs *Mafs) Tokens(n Node) state.State

Tokens returns the tokenarray registered with node n.

type MafsMessage 

type MafsMessage struct {
	SenderID int
	State    []int // SharedState
	G        int
	H        int
}

MafsMessage contains a search state, and other information

type MafsNode 

type MafsNode struct {
	// contains filtered or unexported fields
}

MafsNode is the node type for mafs search implementing search.Node interface

func (*MafsNode) Action 

func (n *MafsNode) Action() *task.Action

Action returns the nodes creating action

func (*MafsNode) G 

func (n *MafsNode) G() int

G is the g-value accessor to satisfy ValueNode interface

func (*MafsNode) H 

func (n *MafsNode) H() int

H is the h-value accessor to satisfy ValueNode interface

func (*MafsNode) ID 

func (n *MafsNode) ID() state.StateID

ID returns the stateID the node is associated with uniquely

func (*MafsNode) Parent 

func (n *MafsNode) Parent() Node

Parent returns the nodes parent node

func (*MafsNode) String 

func (n *MafsNode) String() string

type Move 

type Move struct {
	T      int // discrete time
	Action *task.Action
}

Move represents the application of an action at a certain point in time

type Node 

type Node interface {
	ID() state.StateID
	Parent() Node
	Action() *task.Action
}

Node interface all search nodes should implement

type NodeAccessor 

type NodeAccessor interface {
	HasNode(state.StateID) (Node, bool)
	Tokens(Node) state.State
}

NodeAccessor contains methods to access nodes

type NodeGetter 

type NodeGetter interface {
	Get(int) ValueNode
}

NodeGetter instances can access an element at index i with Get(i)

type NodeQueue 

type NodeQueue interface {
	Len() int
	Put(interface{})
	Take() interface{}
}

type PhonyPruner 

type PhonyPruner struct{}

PhonyPruner does not prune anything

func NewPhonyPruner 

func NewPhonyPruner(t *task.Task) *PhonyPruner

NewPhonyPruner returns a new PhonyPruner instance

func (*PhonyPruner) Prune 

func (*PhonyPruner) Prune(s *state.State, ops []*task.Action) []*task.Action

Prune does not prune anything (its just the identity of ops)

type Plan 

type Plan []Move

Plan consists of Moves of an agent

func (Plan) Cost 

func (p Plan) Cost(ct task.CostType) int

Cost returns the sum of all action costs of the plan

func (Plan) Reversed 

func (p Plan) Reversed(maxStep int) Plan

Reverse reverses a plan given the total number of steps among all agents (each agents plan might be shorter).

func (Plan) String 

func (p Plan) String() string

type PlanExtractionMessage 

type PlanExtractionMessage struct {
	SenderID int
	Step     int
	Tokens   []int
	Msg      string
}

PlanExtractionMessage is used for distributed plan extraction procedure. The message means that during planning, the sender (with senderID) has received a state from the other agent containing stateID in the tokenlist. The other agent can lookup the stateID and tokens to continue plan extraction from there.

type PlanExtractor 

type PlanExtractor struct {
	// contains filtered or unexported fields
}

func (*PlanExtractor) Extract 

func (x *PlanExtractor) Extract(n Node)

Extract the plan steps of this agent, then ask other agents for their parts.

func (*PlanExtractor) Msg 

func (x *PlanExtractor) Msg() *XMessage

type PlanRegistry 

type PlanRegistry struct {
	// contains filtered or unexported fields
}

func NewPlanRegistry 

func NewPlanRegistry(e *Engine) *PlanRegistry

func (*PlanRegistry) BestCostPlan 

func (pr *PlanRegistry) BestCostPlan() Plan

func (*PlanRegistry) BestMakespanPlan 

func (pr *PlanRegistry) BestMakespanPlan() (string, Plan)

func (*PlanRegistry) NumPlans 

func (pr *PlanRegistry) NumPlans() int

func (*PlanRegistry) Start 

func (pr *PlanRegistry) Start(n Node, costtype task.CostType)

Start extracting a plan leading to the goal node n.

type PriorityQueue 

type PriorityQueue []ValueNode

A PriorityQueue implements heap.Interface and holds ValueNodes

func NewPriorityQueue 

func NewPriorityQueue() *PriorityQueue

func (*PriorityQueue) Get 

func (q *PriorityQueue) Get(i int) ValueNode

Get returns node at index i (NodeGetter interface)

func (PriorityQueue) Len 

func (q PriorityQueue) Len() int

func (PriorityQueue) Less 

func (q PriorityQueue) Less(i, j int) bool

func (*PriorityQueue) Pop 

func (q *PriorityQueue) Pop() interface{}

Pop removes the first element from the queue

func (*PriorityQueue) Push 

func (q *PriorityQueue) Push(x interface{})

Push adds a new element to the queue

func (*PriorityQueue) Put 

func (q *PriorityQueue) Put(x interface{})

func (PriorityQueue) Swap 

func (q PriorityQueue) Swap(i, j int)

func (*PriorityQueue) Take 

func (q *PriorityQueue) Take() interface{}

type PriorityQueueFIFO 

type PriorityQueueFIFO struct {
	// contains filtered or unexported fields
}

Queue for A* search

func NewPriorityQueueFIFO 

func NewPriorityQueueFIFO() *PriorityQueueFIFO

func (*PriorityQueueFIFO) Get 

func (q *PriorityQueueFIFO) Get(i int) ValueNode

Get returns node at index i (NodeGetter interface)

func (PriorityQueueFIFO) Len 

func (q PriorityQueueFIFO) Len() int

func (PriorityQueueFIFO) Less 

func (q PriorityQueueFIFO) Less(i, j int) bool

func (*PriorityQueueFIFO) Pop 

func (q *PriorityQueueFIFO) Pop() interface{}

Pop removes the first element from the queue

func (*PriorityQueueFIFO) Push 

func (q *PriorityQueueFIFO) Push(n interface{})

Push adds a new element to the queue

func (*PriorityQueueFIFO) Put 

func (q *PriorityQueueFIFO) Put(x interface{})

func (PriorityQueueFIFO) Swap 

func (q PriorityQueueFIFO) Swap(i, j int)

func (*PriorityQueueFIFO) Take 

func (q *PriorityQueueFIFO) Take() interface{}

type ProgressInfo 

type ProgressInfo struct {
	// contains filtered or unexported fields
}

ProgressInfo collects information on search progress

func NewProgressInfo 

func NewProgressInfo(agentID int, agents comm.ConnList, l *log.Logger) *ProgressInfo

NewProgressInfo creates a new ProgressInfo object

func (*ProgressInfo) Print 

func (i *ProgressInfo) Print()

Print prints the current progress to stdout

func (*ProgressInfo) PrintCurrent 

func (i *ProgressInfo) PrintCurrent()

PrintCurrent prints the current progress to stdout (same as Print) but is used to report progress after a given duration

func (*ProgressInfo) PrintTime 

func (i *ProgressInfo) PrintTime()

PrintTime prints the time (in minutes) since the object was created

func (*ProgressInfo) SetPlan 

func (i *ProgressInfo) SetPlan(plan *PlanExtractor)

SetPlan that this progress information is about.

func (*ProgressInfo) SummaryJSON 

func (i *ProgressInfo) SummaryJSON() string

SummaryJSON summarizes the progress as JSON string.

type StateActionMessage 

type StateActionMessage struct {
	SenderID int
	State    []int // SharedState
	Actions  []int
	Costs    []int
	H        int
}

StateActionMessage contains a search state, actions, and other information

func (*StateActionMessage) G 

func (m *StateActionMessage) G() int

type Status 

type Status int

Status represents a search strategy state

type Strategy 

type Strategy interface {
	// Initialize is called once before the search starts and contains all the
	// required initialization logic.
	Initialize()

	// Step is continiously called in the search.Engine's main loop. It executes
	// a single search step and returns the new search status.
	Step() Status
}

Strategy is the basic search strategy interface

func NewDmtBfs 

func NewDmtBfs(e *Engine, opts *opt.OptionSet) Strategy

NewDmtBfs returns a greedy dmt strategy

func NewDmtGus 

func NewDmtGus(e *Engine, opts *opt.OptionSet) Strategy

NewDmtGus returns a balanced (uct-like) dmt strategy

func NewDmtMakespanBfs 

func NewDmtMakespanBfs(e *Engine, opts *opt.OptionSet) Strategy

NewDmtMakespanBfs returns a greedy dmt strategy

func NewDmtUCB1 

func NewDmtUCB1(e *Engine, opts *opt.OptionSet) Strategy

NewDmtUCB1 returns a balanced (uct-like) dmt strategy

func NewMafs 

func NewMafs(e *Engine, opts *opt.OptionSet) Strategy

NewMafs creates a new mafs (multi-agent forward search) strategy

func NewStrategy 

func NewStrategy(engine *Engine, args []string) Strategy

ParseStrategy retrieves the specified strategy from the strategyRegistry (if the respective strategy was registered before), parses its command line options, then builds and returns the specified Strategy

func NewWeightedDmtMakespan 

func NewWeightedDmtMakespan(e *Engine, opts *opt.OptionSet) Strategy

NewWeightedDmtMakespan creates a weighted, greedy dmt strategy

type StrategyInfo 

type StrategyInfo struct {
	Name        string
	Description string
	NewStrategy func(*Engine, *opt.OptionSet) Strategy
	Options     *opt.OptionSet
}

StrategyInfo holds information necessary for strategy creation based on command line arguments. For each search strategy selectable via cmd arguments, an according StrategyInfo object must exist in the (global) strategyRegistry

func GetStrategy 

func GetStrategy(name string) (*StrategyInfo, error)

GetStrategy returns the strategyinfo registered with the provided name (= name of the strategy, as used in the command line argument)

type StubbornSets 

type StubbornSets struct {
	// contains filtered or unexported fields
}

StubbornSets is the `superclass` type, that is embedded by all concrete StubbornSets types (like StubbornSetsSimple or StubbornSetsEC). It provides all common methods (and instance variables) between the different implementations of stubborn sets.

func NewStubbornSets 

func NewStubbornSets(t *task.Task) *StubbornSets

NewStubbornSets creates a new StubbornSets object

type StubbornSetsSimple 

type StubbornSetsSimple struct {
	*StubbornSets
	// contains filtered or unexported fields
}

StubbornSetsSimple implements simple stubborn set computation

func NewStubbornSetsSimple 

func NewStubbornSetsSimple(t *task.Task) *StubbornSetsSimple

NewStubbornSetsSimple builds and returns a new StubbornSetsSimple object

func (*StubbornSetsSimple) Prune 

func (ss *StubbornSetsSimple) Prune(s *state.State, actions []*task.Action) []*task.Action

Prune takes a state and a set of actions and returns a subset of these actions. Actions not contained in that set can be pruned during search.

type TextMessage 

type TextMessage struct {
	SenderID int
	Msg      string
}

TextMessage is the message type for sending strings

type ValueNode 

type ValueNode interface {
	Node
	H() int
	G() int
}

type XMessage 

type XMessage struct {
	SenderID      int
	Descriptor    string // = AgentID+GoalSID of extraction initiator
	CurrentState  []int
	CurrentStep   int
	TotalCost     int
	TotalMakespan int
	Msg           string
}

XMessage = plan extraction message

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.