Implementation of SearchStrategy by usage of Beam Search. More...

#include <beam_search_strategy.hpp>

Inheritance diagram for arbitrator::BeamSearchStrategy:

Collaboration diagram for arbitrator::BeamSearchStrategy:

Public Member Functions
	BeamSearchStrategy (int beam_width)
	Constructor for BeamSearchStrategy. More...

std::vector< std::pair< carma_planning_msgs::msg::ManeuverPlan, double > >	prioritize_plans (std::vector< std::pair< carma_planning_msgs::msg::ManeuverPlan, double > > plans) const
	Prioritize the plans and eliminate those outside the beam width. More...

Public Member Functions inherited from arbitrator::SearchStrategy
virtual std::vector< std::pair< carma_planning_msgs::msg::ManeuverPlan, double > >	prioritize_plans (std::vector< std::pair< carma_planning_msgs::msg::ManeuverPlan, double > > plans) const =0
	Sort the list of plans in the open-set by priority. More...

virtual	~SearchStrategy ()
	Virtual destructor provided for memory safety. More...

Private Attributes
int	beam_width_

Detailed Description

Implementation of SearchStrategy by usage of Beam Search.

Beam Search is similar to breadth-first search with the exception that only a certain number of nodes at each step are retained to the next. This is referred to as the "beam width" of the search and is applied to the sorted open list at the end of every search step. This provides a reasonable optimization by ensuring that not all nodes need to be expanded.

A beam width of n=1 is identical to naive greedy search.

A beam width of n=inf is identical to breadth-first search

Definition at line 37 of file beam_search_strategy.hpp.

Constructor & Destructor Documentation

◆ BeamSearchStrategy()

arbitrator::BeamSearchStrategy::BeamSearchStrategy ( int beam_width )

inline

Constructor for BeamSearchStrategy.

Parameters

beam_width The number of nodes to include in the search beam during each depth of the search an infinite value would be equivalent to breadth-first search. A value of 1 is equivalent to naive greedy search.

Definition at line 46 of file beam_search_strategy.hpp.

46 :

47 beam_width_(beam_width) {};

arbitrator::BeamSearchStrategy::beam_width_

int beam_width_

Definition: beam_search_strategy.hpp:56

Member Function Documentation

◆ prioritize_plans()

std::vector< std::pair< carma_planning_msgs::msg::ManeuverPlan, double > > arbitrator::BeamSearchStrategy::prioritize_plans ( std::vector< std::pair< carma_planning_msgs::msg::ManeuverPlan, double > > plans ) const

virtual

Prioritize the plans and eliminate those outside the beam width.

Parameters

plans The plans to evaluate as (plan, cot ) pairs

Returns: The sorted list of up to size beam_width

Implements arbitrator::SearchStrategy.

Definition at line 21 of file beam_search_strategy.cpp.

    {
        std::sort(plans.begin(), 
            plans.end(), 
            [] (const std::pair<carma_planning_msgs::msg::ManeuverPlan, double>& a, const std::pair<carma_planning_msgs::msg::ManeuverPlan, double>& b) 
            {
                return a.second < b.second;
            }
        );
 
        if (plans.size() > beam_width_)
        {
            plans.resize(beam_width_);
        }
        
        return plans;
    }

References beam_width_.

Member Data Documentation

◆ beam_width_

int arbitrator::BeamSearchStrategy::beam_width_

private

Definition at line 56 of file beam_search_strategy.hpp.

Referenced by prioritize_plans().

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

arbitrator/include/beam_search_strategy.hpp
arbitrator/src/beam_search_strategy.cpp

Public Member Functions