Implements a generic A* search algorithm. More...

#include <HeuristicSearch.hpp>

Collaboration diagram for m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >:

Public Types
using	state_type = State

using	expand_type = Expand

using	heuristic_type = Heuristic

using	static_search_config = StaticConfig

using	callback_t = std::function< void(state_type, double)>

using	state_manager_type = StateManager< State, Expand, Heuristic, not(use_beam_search and is_monotone), use_beam_search, StaticConfig, Context... >

Public Member Functions
	genericAStar (Context &... context)

	genericAStar (const genericAStar &)=delete

	genericAStar (genericAStar &&)=default

genericAStar &	operator= (genericAStar &&)=default

const state_manager_type &	state_manager () const

float	weighting_factor () const
	Returns the weighting factor for the heuristic value.

float	weighting_factor (float new_factor)
	Set the weighting factor for the heuristic value and returns the old value.

const State &	search (state_type initial_state, expand_type expand, heuristic_type &heuristic, const SearchConfiguration< StaticConfig > &config, Context &... context)
	Search for a path from the given `initial_state` to a goal state.

void	clear ()
	Resets the state of the search.

void	dump (std::ostream &out) const

void	dump () const

Static Public Attributes
static constexpr bool	use_weighted_search = StaticConfig::PerformWeightedSearch
	‍Whether to perform weighted search with a given weighting factor for the heuristic value

static constexpr float	beam_width = StaticConfig::BeamWidth::num / StaticConfig::BeamWidth::den
	‍The width of a beam used for beam search. Set to 0 to disable beam search.

static constexpr bool	use_beam_search = StaticConfig::BeamWidth::num != 0
	‍Whether to perform beam search or regular A*

static constexpr bool	use_dynamic_beam_sarch = use_beam_search and beam_width < 1.f
	‍Whether to use a dynamic beam width for beam search

static constexpr bool	is_lazy = StaticConfig::Lazy
	‍Whether to evaluate the heuristic lazily

static constexpr bool	is_monotone = StaticConfig::IsMonotone
	‍Whether the state space is acyclic and without dead ends (useful in combination with beam search)

static constexpr float	BEAM_FACTOR = .2f
	‍The fraction of a state's successors to add to the beam (if performing beam search)

static constexpr bool	use_anytime_search = StaticConfig::PerformAnytimeSearch
	‍Whether to search with a fixed, finite budget and return early when the budget is exhausted

Private Member Functions
	DEF_COUNTER (cached_heuristic_value) struct weighted_state
	A state plus its heuristic value.

void	beam (state_type state, double h, Context &... context)

void	beam_dynamic (expand_type &expand, Context &... context)

void	for_each_successor_lazily (callback_t &&callback, const state_type &state, heuristic_type &heuristic, expand_type &expand, Context &... context)
	Expands the given `state` by lazily evaluating the heuristic function.

void	for_each_successor_eagerly (callback_t &&callback, const state_type &state, heuristic_type &heuristic, expand_type &expand, Context &... context)
	Expands the given `state` by eagerly evaluating the heuristic function.

void	for_each_successor (callback_t &&callback, const state_type &state, heuristic_type &heuristic, expand_type &expand, Context &... context)
	Expands the given `state` according to `is_lazy`.

void	explore_state (const state_type &state, heuristic_type &heuristic, expand_type &expand, Context &... context)
	Explores the given `state`.

Private Attributes
float	weighting_factor_ = 1.
	‍the weighting factor for the heuistic value of a state

state_manager_type	state_manager_
	‍the search's state manager, tracking heuristic value, checking for duplicates, and ordering by f-value

std::vector< weighted_state >	candidates
	‍candidates for the beam

Friends
std::ostream &	operator<< (std::ostream &out, const genericAStar &AStar)

Detailed Description

template<heuristic_search_state State, typename Expand, typename Heuristic, SearchConfigConcept StaticConfig, typename... Context>
requires heuristic_search_heuristic<Heuristic, Context...>
struct m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >

Implements a generic A* search algorithm.

Allows for specifying a weighting factor for the heuristic value. Allows for lazy evaluation of the heuristic.

Definition at line 620 of file HeuristicSearch.hpp.

Member Typedef Documentation

◆ callback_t

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

using m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::callback_t = std::function<void(state_type, double)>

Definition at line 644 of file HeuristicSearch.hpp.

◆ expand_type

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

using m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::expand_type = Expand

Definition at line 623 of file HeuristicSearch.hpp.

◆ heuristic_type

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

using m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::heuristic_type = Heuristic

Definition at line 624 of file HeuristicSearch.hpp.

◆ state_manager_type

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

using m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::state_manager_type = StateManager< State, Expand, Heuristic, not (use_beam_search and is_monotone), use_beam_search, StaticConfig, Context... >

Definition at line 646 of file HeuristicSearch.hpp.

◆ state_type

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

using m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::state_type = State

Definition at line 622 of file HeuristicSearch.hpp.

◆ static_search_config

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

using m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::static_search_config = StaticConfig

Definition at line 625 of file HeuristicSearch.hpp.

Constructor & Destructor Documentation

◆ genericAStar() [1/3]

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::genericAStar ( Context &... context )

inlineexplicit

Definition at line 705 of file HeuristicSearch.hpp.

◆ genericAStar() [2/3]

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::genericAStar ( const genericAStar< State, Expand, Heuristic, StaticConfig, Context > & )

delete

◆ genericAStar() [3/3]

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::genericAStar ( genericAStar< State, Expand, Heuristic, StaticConfig, Context > && )

default

Member Function Documentation

◆ beam()

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

void m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::beam	(	state_type	state,
		double	h,
		Context &...	context
	)

inlineprivate

Definition at line 752 of file HeuristicSearch.hpp.

References M_insist, and m::ai::StateManager< State, Expand, Heurisitc, HasRegularQueue, HasBeamQueue, Config, Context >::push_regular_queue().

◆ beam_dynamic()

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

void m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::beam_dynamic	(	expand_type &	expand,
		Context &...	context
	)

inlineprivate

Definition at line 787 of file HeuristicSearch.hpp.

References M_insist, m::ai::StateManager< State, Expand, Heurisitc, HasRegularQueue, HasBeamQueue, Config, Context >::push_beam_queue(), and m::ai::StateManager< State, Expand, Heurisitc, HasRegularQueue, HasBeamQueue, Config, Context >::push_regular_queue().

◆ clear()

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

void m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::clear ( )

inline

Resets the state of the search.

Definition at line 740 of file HeuristicSearch.hpp.

References m::ai::StateManager< State, Expand, Heurisitc, HasRegularQueue, HasBeamQueue, Config, Context >::clear().

◆ DEF_COUNTER()

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::DEF_COUNTER ( cached_heuristic_value )

inlineprivate

A state plus its heuristic value.

Definition at line 673 of file HeuristicSearch.hpp.

◆ dump() [1/2]

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

void m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::dump ( ) const

inline

Definition at line 890 of file HeuristicSearch.hpp.

References m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::dump().

Referenced by m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::dump().

◆ dump() [2/2]

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

void m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::dump ( std::ostream & out ) const

inline

Definition at line 889 of file HeuristicSearch.hpp.

◆ explore_state()

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

void m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::explore_state	(	const state_type &	state,
		heuristic_type &	heuristic,
		expand_type &	expand,
		Context &...	context
	)

inlineprivate

Explores the given state.

Definition at line 855 of file HeuristicSearch.hpp.

◆ for_each_successor()

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

void m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::for_each_successor	(	callback_t &&	callback,
		const state_type &	state,
		heuristic_type &	heuristic,
		expand_type &	expand,
		Context &...	context
	)

inlineprivate

Expands the given state according to is_lazy.

Definition at line 845 of file HeuristicSearch.hpp.

◆ for_each_successor_eagerly()

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

void m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::for_each_successor_eagerly	(	callback_t &&	callback,
		const state_type &	state,
		heuristic_type &	heuristic,
		expand_type &	expand,
		Context &...	context
	)

inlineprivate

Expands the given state by eagerly evaluating the heuristic function.

Definition at line 824 of file HeuristicSearch.hpp.

◆ for_each_successor_lazily()

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

void m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::for_each_successor_lazily	(	callback_t &&	callback,
		const state_type &	state,
		heuristic_type &	heuristic,
		expand_type &	expand,
		Context &...	context
	)

inlineprivate

Expands the given state by lazily evaluating the heuristic function.

Definition at line 804 of file HeuristicSearch.hpp.

References m::ai::StateManager< State, Expand, Heurisitc, HasRegularQueue, HasBeamQueue, Config, Context >::end(), and m::ai::StateManager< State, Expand, Heurisitc, HasRegularQueue, HasBeamQueue, Config, Context >::find().

◆ operator=()

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

genericAStar & m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::operator= ( genericAStar< State, Expand, Heuristic, StaticConfig, Context > && )

default

◆ search()

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>
requires heuristic_search_heuristic<Heuristic, Context...>

const State & m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::search	(	state_type	initial_state,
		expand_type	expand,
		heuristic_type &	heuristic,
		const SearchConfiguration< StaticConfig > &	config,
		Context &...	context
	)

Search for a path from the given initial_state to a goal state.

Uses the given heuristic to guide the search. Provides an upper bound for the cost of the shortest path.

Returns: the cost of the computed path from initial_state to a goal state

Definition at line 901 of file HeuristicSearch.hpp.

References m::and, m::ai::SearchConfiguration< StaticConfig >::expansion_budget, M_insist, m::ai::SearchConfiguration< StaticConfig >::upper_bound, and m::ai::SearchConfiguration< StaticConfig >::weighting_factor.

◆ state_manager()

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

const state_manager_type & m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::state_manager ( ) const

inline

Definition at line 719 of file HeuristicSearch.hpp.

◆ weighting_factor() [1/2]

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

float m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::weighting_factor ( ) const

inline

Returns the weighting factor for the heuristic value.

Definition at line 722 of file HeuristicSearch.hpp.

◆ weighting_factor() [2/2]

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

float m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::weighting_factor ( float new_factor )

inline

Set the weighting factor for the heuristic value and returns the old value.

Definition at line 725 of file HeuristicSearch.hpp.

References M_insist.

Friends And Related Function Documentation

◆ operator<<

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

std::ostream & operator<<	(	std::ostream &	out,
		const genericAStar< State, Expand, Heuristic, StaticConfig, Context > &	AStar
	)

friend

Definition at line 884 of file HeuristicSearch.hpp.

Field Documentation

◆ BEAM_FACTOR

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

constexpr float m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::BEAM_FACTOR = .2f

staticconstexpr

‍The fraction of a state's successors to add to the beam (if performing beam search)

Definition at line 640 of file HeuristicSearch.hpp.

◆ beam_width

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

constexpr float m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::beam_width = StaticConfig::BeamWidth::num / StaticConfig::BeamWidth::den

staticconstexpr

‍The width of a beam used for beam search. Set to 0 to disable beam search.

Definition at line 630 of file HeuristicSearch.hpp.

◆ candidates

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

std::vector<weighted_state> m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::candidates

private

‍candidates for the beam

Definition at line 702 of file HeuristicSearch.hpp.

◆ is_lazy

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

constexpr bool m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::is_lazy = StaticConfig::Lazy

staticconstexpr

‍Whether to evaluate the heuristic lazily

Definition at line 636 of file HeuristicSearch.hpp.

◆ is_monotone

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

constexpr bool m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::is_monotone = StaticConfig::IsMonotone

staticconstexpr

‍Whether the state space is acyclic and without dead ends (useful in combination with beam search)

Definition at line 638 of file HeuristicSearch.hpp.

◆ state_manager_

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

state_manager_type m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::state_manager_

private

‍the search's state manager, tracking heuristic value, checking for duplicates, and ordering by f-value

Definition at line 699 of file HeuristicSearch.hpp.

◆ use_anytime_search

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

constexpr bool m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::use_anytime_search = StaticConfig::PerformAnytimeSearch

staticconstexpr

‍Whether to search with a fixed, finite budget and return early when the budget is exhausted

Definition at line 642 of file HeuristicSearch.hpp.

◆ use_beam_search

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

constexpr bool m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::use_beam_search = StaticConfig::BeamWidth::num != 0

staticconstexpr

‍Whether to perform beam search or regular A*

Definition at line 632 of file HeuristicSearch.hpp.

◆ use_dynamic_beam_sarch

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

constexpr bool m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::use_dynamic_beam_sarch = use_beam_search and beam_width < 1.f

staticconstexpr

‍Whether to use a dynamic beam width for beam search

Definition at line 634 of file HeuristicSearch.hpp.

◆ use_weighted_search

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

constexpr bool m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::use_weighted_search = StaticConfig::PerformWeightedSearch

staticconstexpr

‍Whether to perform weighted search with a given weighting factor for the heuristic value

Definition at line 628 of file HeuristicSearch.hpp.

◆ weighting_factor_

template<heuristic_search_state State, typename Expand , typename Heuristic , SearchConfigConcept StaticConfig, typename... Context>

float m::ai::genericAStar< State, Expand, Heuristic, StaticConfig, Context >::weighting_factor_ = 1.

private

‍the weighting factor for the heuistic value of a state

Definition at line 658 of file HeuristicSearch.hpp.

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

include/mutable/util/HeuristicSearch.hpp

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ callback_t

◆ expand_type

◆ heuristic_type

◆ state_manager_type

◆ state_type

◆ static_search_config

Constructor & Destructor Documentation

◆ genericAStar() [1/3]

◆ genericAStar() [2/3]

◆ genericAStar() [3/3]

Member Function Documentation

◆ beam()

◆ beam_dynamic()

◆ clear()

◆ DEF_COUNTER()

◆ dump() [1/2]

◆ dump() [2/2]

◆ explore_state()

◆ for_each_successor()

◆ for_each_successor_eagerly()

◆ for_each_successor_lazily()

◆ operator=()

◆ search()

◆ state_manager()

◆ weighting_factor() [1/2]

◆ weighting_factor() [2/2]

Friends And Related Function Documentation

◆ operator<<

Field Documentation

◆ BEAM_FACTOR

◆ beam_width

◆ candidates

◆ is_lazy

◆ is_monotone

◆ state_manager_

◆ use_anytime_search

◆ use_beam_search

◆ use_dynamic_beam_sarch

◆ use_weighted_search

◆ weighting_factor_