A parallel heuristic for the energy optimization of robotic cells. More...

#include <ParallelHeuristicSolver.h>

Collaboration diagram for ParallelHeuristicSolver:

Public Member Functions
	ParallelHeuristicSolver (const RoboticLine &l, const PrecalculatedMapping &m)
	It initializes the heuristic, i.e. preallocates some arrays, calculates the length of the tabu list, etc. More...

Solution	solve ()
	It optimizes the robotic cell and returns the best found solution. More...

Private Member Functions
void	controlThread ()
	Generates various alternatives, launches worker threads, prints progress info, joins the workers, and handles errors of workers. More...

void	workerThread (uint32_t threadId, std::vector< std::vector< CircuitRecord >> initialCircuits, PrecalculatedCircuits precalculatedCircuits)
	The worker thread generates initial tuples, and optimizes them by local modifications proposed by sub-heuristics. More...

Graph	constructMinimalDurationGraph (Robot *r) const
	Generates a distance graph for the given robot. More...

DistanceMatrix< double >	createInitialDistanceMatrix (const Graph &g) const
	It creates an initial matrix of distances based on edge lengths. More...

std::vector< CircuitRecord >	generateRandomAlternatives (const uint32_t &threadId, const Graph &g, const DistanceMatrix< double > &m)
	Generates some random alternatives, i.e. candidates for a feasible order, from a distance graph and distance matrix of a robot. More...

HamiltonianCircuit< Location >	getShortestCircuit (const uint32_t &threadId, const std::vector< StaticActivity * > &circuit, const std::vector< Location * > &fixed, bool writeCircuit=true)
	It calculates the shortest circuit through locations that visits each static activity in the same order as it is in circuit parameter. More...

std::vector< std::vector< CircuitRecord > >	generateShortestCircuits (PrecalculatedCircuits &precalculatedCircuits)
	It finds random alternatives for each robot and calculates their shortest closed paths through locations. More...

uint32_t	selectAlternative (const std::vector< CircuitRecord > &alternatives) const
	It randomly selects a robot alternative according to a distribution function that slightly prefers the alternatives with lower estimation of the robot cycle time. More...

double	calculateNewCycleTime (const uint32_t &threadId, const double &currentCycleTime, std::vector< StaticActivity * > &alternative, std::vector< Location * > &fixed, Location *toFix, PrecalculatedCircuits &precalculatedCircuits)
	A highly optimized function calculates a lower estimation on the robot cycle time if toFix location is newly fixed. More...

void	addRandomTuplesToKB (const uint32_t &threadId, const uint32_t &numOfTuples, std::vector< std::vector< CircuitRecord >> &initialCircuits, PrecalculatedCircuits &precalculatedCircuits)
	It generates and adds a requested number of tuples to the KnowledgeBase. More...

void	generatePromisingTuples (const uint32_t &threadId)
	It generates promising tuples and adds them to the KnowledgeBase. More...

double	changeRobotPaths (uint32_t threadId, const CircuitTuple &t, PartialSolution &ps, const std::vector< std::vector< Location * >> &fixed)
	It randomly modifies the robot paths to enable the heuristic to search otherwise unreachable parts of the solution space. More...

void	printProgressInfo (const double &currentRuntime)
	Prints various information about the performance of the sub-heuristics, generation of tuples, and solving reduced problems by Linear Programming. More...

void	writePerformanceRecordToLogFile (const double &initializationTime, const double &finalRuntime)
	It writes various statistics about the heuristic performance to a CSV file. More...

Static Private Member Functions
static double	penaltyFunction (const double &minCycle, const double &demandedCycleTime)
	The function expressing the risk of exceeding the robot cycle time depending on its lower estimation. More...

Private Attributes
double	mRuntime
	The runtime of this heuristic, updated from time to time.

uint32_t	mTabuListSize
	The number of tabu list elements calculated in the constructor.

std::atomic< bool >	mFeasible
	Used to stop other OpenMP threads if the instance infeasibility is detected by a thread.

std::atomic< bool >	mStopCondition
	The control thread sets this flag to true to stop all the worker threads.

RoboticLine	mLine
	Robotic cell to be optimized.

KnowledgeBase	mKB
	Various data of the heuristic, e.g. generated tuples, performance statistics, etc.

PrecalculatedMapping	mMapping
	Fast searching in the data structure of the robotic cell.

HeuristicAlgorithms	algo
	Optimization sub-heuristics and the related Linear Programming solver for partially fixed problems.

std::vector< std::vector< std::vector< double > > >	mDist
	Preallocated 2-D array of distances for getShortestCircuit method, indexed by thread.

std::vector< std::vector< std::vector< int64_t > > >	mPreds
	Preallocated 2-D array of predecessors for getShortestCircuit method, indexed by thread.

std::vector< std::vector< std::vector< Location * > > >	mLocs
	Preallocated 2-D array of locations for getShortestCircuit method, indexed by thread.

std::vector< SpatialCmpTuple >	mSortedSptCmp
	The vector of spatial compatibility pairs heuristically sorted in decreasing order of difficulty.

Detailed Description

A parallel heuristic for the energy optimization of robotic cells.

A parallel hybrid heuristic that solves the energy optimization problem of robotic cells is implemented in this class. At first the heuristic generates a candidate tuples, i.e. a partially fixed problems, that could be resulting in initial feasible solutions. If an initial solution is feasible then it is further optimized by sub-heuristics that iteratively change the fixed locations and power saving modes with respect to the energy reasoning. The best found solution is returned after a given time limit, or an exception is thrown if such a solution does not exist.

See also: HeuristicAlgorithms, KnowledgeBase

Definition at line 46 of file ParallelHeuristicSolver.h.

Constructor & Destructor Documentation

ParallelHeuristicSolver::ParallelHeuristicSolver	(	const RoboticLine &	l,
		const PrecalculatedMapping &	m
	)

It initializes the heuristic, i.e. preallocates some arrays, calculates the length of the tabu list, etc.

Parameters

l	Robotic cell to be optimized.
m	A mapping calculated for the given robotic cell that enables fast searching.

Definition at line 38 of file ParallelHeuristicSolver.cpp.

Member Function Documentation

void ParallelHeuristicSolver::addRandomTuplesToKB	(	const uint32_t &	threadId,
		const uint32_t &	numOfTuples,
		std::vector< std::vector< CircuitRecord >> &	initialCircuits,
		PrecalculatedCircuits &	precalculatedCircuits
	)

private

It generates and adds a requested number of tuples to the KnowledgeBase.

Parameters

threadId	Thread identification, i.e. a number between 0 and n-1 where n is the total number of executed threads.
numOfTuples	The number of candidate tuples, i.e. partially fixed problems, to be generated.
initialCircuits	Alternatives and the related fixed locations and shortest paths through locations, indexed by robot.
precalculatedCircuits	ShortestCircuit to the fastest closed path through robot locations (including the fixed ones).

Definition at line 738 of file ParallelHeuristicSolver.cpp.

double ParallelHeuristicSolver::calculateNewCycleTime	(	const uint32_t &	threadId,
		const double &	currentCycleTime,
		std::vector< StaticActivity * > &	alternative,
		std::vector< Location * > &	fixed,
		Location *	toFix,
		PrecalculatedCircuits &	precalculatedCircuits
	)

private

A highly optimized function calculates a lower estimation on the robot cycle time if toFix location is newly fixed.

Parameters

threadId	Thread identification, i.e. a number between 0 and n-1 where n is the total number of executed threads.
currentCycleTime	Current lower bound on the robot cycle time for the given alternative and fixed locations.
alternative	Considered robot alternative, i.e. the order of static activities.
fixed	Locations that should be fixed to enforce the spatial compatibility.
toFix	A new location to be fixed, it replaces another one in fixed vector.
precalculatedCircuits	ShortestCircuit to the fastest closed path through robot locations (including the fixed ones).

Returns: A lower estimation on the robot cycle time if toFix location is fixed instead of another one in fixed vector.

Definition at line 700 of file ParallelHeuristicSolver.cpp.

double ParallelHeuristicSolver::changeRobotPaths	(	uint32_t	threadId,
		const CircuitTuple &	t,
		PartialSolution &	ps,
		const std::vector< std::vector< Location * >> &	fixed
	)

private

It randomly modifies the robot paths to enable the heuristic to search otherwise unreachable parts of the solution space.

Parameters

threadId	Thread identification, i.e. a number between 1 and n where n is the total number of worker threads.
t	A partially fixed problem to be modified, i.e. tuple.
ps	Fixed locations, movements, and power saving modes.
fixed	Currently fixed locations.

Returns: A lower bound on a robot cycle time after changing robot paths.

Definition at line 898 of file ParallelHeuristicSolver.cpp.

Graph ParallelHeuristicSolver::constructMinimalDurationGraph ( Robot * r ) const

private

Generates a distance graph for the given robot.

Parameters

r	A robot for which a distance graph is created.

Generates a graph where edges are weighted by the minimal possible durations between nodes (static activities). A path from the start node to the end node that visits all the other nodes is a robot alternative.

Definition at line 267 of file ParallelHeuristicSolver.cpp.

void ParallelHeuristicSolver::controlThread ( )

private

Generates various alternatives, launches worker threads, prints progress info, joins the workers, and handles errors of workers.

The control thread starts with the generation of alternatives, i.e. various orders of operations, for individual robots. Afterwards, the worker threads are launched to find good quality solutions. Meanwhile the control thread prints various statistical information about the heuristic performance and generates the promising tuples, i.e. partially fixed problems. After a given time limit, the worker threads are stopped and possible errors, which occurred in worker threads, are reported.

Note: Thread identification of the control thread is 0.

Definition at line 83 of file ParallelHeuristicSolver.cpp.

DistanceMatrix< double > ParallelHeuristicSolver::createInitialDistanceMatrix ( const Graph & g ) const

private

It creates an initial matrix of distances based on edge lengths.

Parameters

g	Distance graph of a robot.

Returns: Initial two-dimensional matrix of distances between graph nodes.

Definition at line 316 of file ParallelHeuristicSolver.cpp.

void ParallelHeuristicSolver::generatePromisingTuples ( const uint32_t & threadId )

private

It generates promising tuples and adds them to the KnowledgeBase.

Parameters

threadId Thread identification. Currently only the control thread (with id 0) generates the promising tuples.

Definition at line 873 of file ParallelHeuristicSolver.cpp.

vector< CircuitRecord > ParallelHeuristicSolver::generateRandomAlternatives	(	const uint32_t &	threadId,
		const Graph &	g,
		const DistanceMatrix< double > &	m
	)

private

Generates some random alternatives, i.e. candidates for a feasible order, from a distance graph and distance matrix of a robot.

Parameters

threadId	Thread identification, i.e. a number between 0 and n-1 where n is the total number of executed threads.
g	Distance graph of a robot for which random alternatives will be searched for.
m	Distance matrix calculated for the given graph.

Returns: Some random alternatives.

Definition at line 330 of file ParallelHeuristicSolver.cpp.

vector< vector< CircuitRecord > > ParallelHeuristicSolver::generateShortestCircuits ( PrecalculatedCircuits & precalculatedCircuits )

private

It finds random alternatives for each robot and calculates their shortest closed paths through locations.

Parameters

precalculatedCircuits ShortestCircuit to the fastest closed path through robot locations (including the fixed ones).

Returns: Random alternatives and their shortest circuits through robot locations for each robot, indexed by robot.

Definition at line 545 of file ParallelHeuristicSolver.cpp.

HamiltonianCircuit< Location > ParallelHeuristicSolver::getShortestCircuit	(	const uint32_t &	threadId,
		const std::vector< StaticActivity * > &	circuit,
		const std::vector< Location * > &	fixed,
		bool	writeCircuit = `true`
	)

private

It calculates the shortest circuit through locations that visits each static activity in the same order as it is in circuit parameter.

Parameters

threadId	Thread identification, i.e. a number between 0 and n-1 where n is the total number of executed threads.
circuit	Closed path through static activities where each static activity of a robot is visited.
fixed	Locations that must be visited to satisfy the spatial compatibility.
writeCircuit	Whether the shortest circuit through locations should be written.

Returns: The shortest circuit through locations (if writeCircuit = true) and its minimal length.

Definition at line 434 of file ParallelHeuristicSolver.cpp.

double ParallelHeuristicSolver::penaltyFunction	(	const double &	minCycle,
		const double &	demandedCycleTime
	)

staticprivate

The function expressing the risk of exceeding the robot cycle time depending on its lower estimation.

Parameters

minCycle	A lower bound on the robot cycle time.
demandedCycleTime	A desired robot cycle time.

Returns: A penalty value quantifying the risk of exceeding the demanded robot cycle time.

See also: generateShortestCircuits, addRandomTuplesToKB

Definition at line 629 of file ParallelHeuristicSolver.cpp.

void ParallelHeuristicSolver::printProgressInfo ( const double & currentRuntime )

private

Prints various information about the performance of the sub-heuristics, generation of tuples, and solving reduced problems by Linear Programming.

Parameters

currentRuntime Current execution time of the heuristic.

Definition at line 941 of file ParallelHeuristicSolver.cpp.

uint32_t ParallelHeuristicSolver::selectAlternative ( const std::vector< CircuitRecord > & alternatives ) const

private

It randomly selects a robot alternative according to a distribution function that slightly prefers the alternatives with lower estimation of the robot cycle time.

Parameters

alternatives Alternatives of a robot.

Returns: Index of the selected alternative (the order of operations).

Definition at line 641 of file ParallelHeuristicSolver.cpp.

Solution ParallelHeuristicSolver::solve ( )

It optimizes the robotic cell and returns the best found solution.

See also: Settings

Definition at line 64 of file ParallelHeuristicSolver.cpp.

void ParallelHeuristicSolver::workerThread	(	uint32_t	threadId,
		std::vector< std::vector< CircuitRecord >>	initialCircuits,
		PrecalculatedCircuits	precalculatedCircuits
	)

private

The worker thread generates initial tuples, and optimizes them by local modifications proposed by sub-heuristics.

Parameters

threadId	Identification of the thread, i.e. a number from 1 to n where n is the total number of worker threads.
initialCircuits	Various alternatives (orders of operations) for each robot, indexed by robots.
precalculatedCircuits	ShortestCircuit to the fastest closed path through robot locations (including the fixed ones).

The worker thread generates candidate tuples, i.e. partially fixed problems that could be resulting in feasible solutions, to be optimized. First of all, the tuple is loaded and an initial timing can be extracted from a solution of Linear Programming. If the timing can be obtained, the optimization phase starts and the sub-heuristics iteratively modifies the tuple in a way that could be resulting in an energy reduction. All the feasible solutions are passed to KnowledgeBase, where the list of elite solutions is located.

See also: HeuristicAlgorithms, MovingAverage, OptimalTiming, Settings

Definition at line 156 of file ParallelHeuristicSolver.cpp.

void ParallelHeuristicSolver::writePerformanceRecordToLogFile	(	const double &	initializationTime,
		const double &	finalRuntime
	)

private

It writes various statistics about the heuristic performance to a CSV file.

Parameters

initializationTime	The time needed for the generation of robot alternatives and their shortest circuits through locations.
finalRuntime	The total real time required by the heuristic.

Definition at line 970 of file ParallelHeuristicSolver.cpp.

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

/home/bukatlib/Downloads/SolverEquationsGeneratedAsImages/inc/HeuristicSolver/ParallelHeuristicSolver.h
/home/bukatlib/Downloads/SolverEquationsGeneratedAsImages/src/HeuristicSolver/ParallelHeuristicSolver.cpp

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation