advertisement

advertisement

Information about CHAC Algorithm ECAL'07 Presentation

Published on September 19, 2007

Author: Slidemora

Source: slideshare.net

These are the slides of the presentation of our implemented Algorithm which solves the Bi-Criteria Military Pathfinding Problem.

advertisement

INDEX Prob lem Description CHAC Algorithm Other Algorithms Tested Experiments and Results Conclusions and Future Work

Prob lem Description

CHAC Algorithm

Other Algorithms Tested

Experiments and Results

Conclusions and Future Work

Problem Description THE UNIT The Military Unit of our problem is composed by soldiers and vehicles , and has some properties: The unit only moves, from an origin to a target point, consuming energy and resources, and avoiding enemies and dangerous zones in the battlefield. level of energy : health of soldiers status of vehicles level of resources : food, medicines, supplies, fuel no weapon

level of energy :

health of soldiers

status of vehicles

level of resources : food, medicines, supplies, fuel

no weapon

Problem Description The Map (scenario) of the problem is a grid of hexagonal cells which models a battlefield. the unit is located in an origin point the unit must reach a target point there may exist one or more enemies there may exist some enemy weapons impact zones FEATURES OF THE MAP

the unit is located in an origin point

the unit must reach a target point

there may exist one or more enemies

there may exist some enemy weapons impact zones

Problem Description Each cell has some properties: X and Y coordinates. Type normal, water, forest, obstacle. Subtype enemy location, origin and destination point, weapons impact. Height value in [-3,3]. Cost in Resources difficulty of going through it. Cost in Energy no combat casualties, damage of vehicles. Lethality energy consumption due to weapons impact in the cell. THE CELLS

Each cell has some properties:

X and Y coordinates.

Type normal, water, forest, obstacle.

Subtype enemy location, origin and destination point, weapons impact.

Height value in [-3,3].

Cost in Resources difficulty of going through it.

Cost in Energy no combat casualties, damage of vehicles.

Lethality energy consumption due to weapons impact in the cell.

Problem Description In this implementation, we can use ‘real’ maps as problem scenarios by defining an underlying information layer . REALISTIC MAPS

Problem Description There is a natural obstacle between two cells when there is a height difference greater than 2 between them. The unit cannot go throught that obstacle. Each cell corresponds to a 500x500 meters zone (real deployed unit size). The line of sight has been implemented in a realistic way. We consider the adquisition capability (the longest distance a unit can see). It limits the line of sight for the enemies and for the problem unit. REALISTIC FEATURES

There is a natural obstacle between two cells when there is a height difference greater than 2 between them. The unit cannot go throught that obstacle.

Each cell corresponds to a 500x500 meters zone (real deployed unit size).

The line of sight has been implemented in a realistic way.

We consider the adquisition capability (the longest distance a unit can see). It limits the line of sight for the enemies and for the problem unit.

Problem Description Example of adquisition capability and natural obstacles: EXAMPLE OF REALISTIC FEATURES

Problem Description The problem is defined as: The criteria for the best path is defined by the user , so it can be the fastest one (minimizing cost in resources), the safest one (minimizing cost in energy and unit visibility for the enemy) , or it can be a combination of both criteria. These objectives are independent, so the problem can be considered as a multiobjective problem . Find the best path for a military unit, from an origin to a destination point inside a battlefield, where there may be some enemies watching over and even firing against the unit. The path must minimize the cost in energy and resources for the unit. DEFINITION

CHAC Algorithm It is a MultiObjective Ant Colony Optimization algorithm (MOACO). There are two independent objectives: speed (fast/low cost in resources path) and safety (safe/low cost in energy path). The problem is transformed into a graph with weighted edges. Each cell corresponds to a node and is connected with its (6) neighbours through edges. There are two weights in each edge. CHAC means ‘ C ompañía de H ormigas AC orazadas’ in spanish. (Armoured Ant Company in english) We refer to the algorithm adapted to a grid of hexagons as Hexa-CHAC (or hCHAC) . INTRODUCTION

CHAC Algorithm hCHAC is an Ant Colony System algorithm adapted to deal with 2 objectives . So we can use the q 0 parameter to balance the exploration and exploitation in the search. it uses only one colony there are 2 pheromone matrices there are 2 heuristic functions there is a parameter, (0,1) which sets the relative importance (priority) of each objective . It is used in the state transition rule to choose the next node in the solution path that an ant is building. MAIN FEATURES

hCHAC is an Ant Colony System algorithm adapted to deal with 2 objectives .

So we can use the q 0 parameter to balance the exploration and exploitation in the search.

it uses only one colony

there are 2 pheromone matrices

there are 2 heuristic functions

there is a parameter, (0,1) which sets the relative importance (priority) of each objective . It is used in the state transition rule to choose the next node in the solution path that an ant is building.

CHAC Algorithm We have implemented 2 state transition rules (2 different hCHAC algorithms) based in the pseudo-random proportional rule usual in ACS (depends on q 0 ). Both use to weight the first objective and (1- ) to weight the second. Combined State Transition Rule (CSTR) Combines the pheromone and heuristic information of both objectives (multiplying them) to calculate the probability of every feasible node. (Similar to proposed by Iredi et al.) Dominance-based State Transition Rule (DSTR) Calculates the probability of every feasible node depending on the number of neighbours it dominates according to pheromone and heuristic information of each objective. STATE TRANSITION RULES

CHAC Algorithm The heuristic functions (one per objective): fast path tries to minimize the distance to target point and the cost in resources safe path tries to minimize the cost in energy and the visibility of the unit The pheromone update (two matrices): local performed every time a node is added to a solution path global performed at the end of an iteration for all the solutions in the Pareto set The cost functions (one per objective): - fast path cost in resources and hidden (little weight). ( Ff ) - safe path cost in energy and hidden (big weight). ( Fs ) OTHER FEATURES

The heuristic functions (one per objective):

fast path tries to minimize the distance to target point and the cost in resources

safe path tries to minimize the cost in energy and the visibility of the unit

The pheromone update (two matrices):

local performed every time a node is added to a solution path

global performed at the end of an iteration for all the solutions in the Pareto set

The cost functions (one per objective):

- fast path cost in resources and hidden (little weight). ( Ff )

- safe path cost in energy and hidden (big weight). ( Fs )

CHAC Algorithm 1. initialization of pheromone matrices with initial amount 2. For i=1 to NUM_iterations 3. For a=1 to NUM_ants 4. sp=build_path(a) 5. evaluate(sp) 6. If sp is non-dominated 7. insert sp in Pareto_Set 8. remove from Pareto_Set dominated solutions 9. Endif 10. EndFor 11. global_pheromone_updating 12. EndFor 13. improve solutions in Pareto_Set PSEUDOCODE

Other Algorithms Extreme Approaches (CSTR and DSTR): extreme fast only consider in the terms for speed. It takes = 1 (only one objective in the state transition rule) extreme safe path only consider terms for safety. It takes = 0 (only one objective in the state transition rule) ** each one using the respective state transition rule ** mono-hCHAC (one objective): Combines both objectives in one. Considers weights in each term. There is only one heuristic function, pheromone matrix and evaluation function. parameter is not used. MOACS (proposed by Baran et al.): It uses only one pheromone matrix for both objectives and two heuristic functions. parameter is used again. PRESENTATION

Extreme Approaches (CSTR and DSTR):

extreme fast only consider in the terms for speed. It takes = 1 (only one objective in the state transition rule)

extreme safe path only consider terms for safety. It takes = 0 (only one objective in the state transition rule)

** each one using the respective state transition rule **

mono-hCHAC (one objective):

Combines both objectives in one. Considers weights in

each term. There is only one heuristic function, pheromone

matrix and evaluation function. parameter is not used.

MOACS (proposed by Baran et al.):

It uses only one pheromone matrix for both objectives and

two heuristic functions. parameter is used again.

Experiments and Results We have tested all the approaches in the same maps, using the same number of iterations and ants. Results are yielded using = 0.9 and = 0.1 (extreme ones considering = 1 and = 0). All of the algorithms yield a set of solutions (they are MO algorithms), excepting mono-objective approach. We show the best solutions for fastest and safest paths. F f is the cost in speed and F s is the cost in safety. PRELIMINARIES

Experiments and Results EXAMPLE MAP. QUANTITATIVE RESULTS

Experiments and Results EXAMPLE MAP. QUANTITATIVE RESULTS (Graphics)

Experiments and Results Fastest ( = 0.9) Ff = 68.5 Fs= 295.4 1500 iterations - 50 ants Safest ( = 0.1) Ff = 80.5 Fs= 7.3 EXAMPLE MAP. hCHAC-CSTR RESULTS

Experiments and Results Fastest ( = 0.9) Ff = 76.0 Fs= 306.1 1500 iterations - 50 ants Safest ( = 0.1) Ff = 95.5 Fs= 9.4 EXAMPLE MAP. hCHAC-DSTR RESULTS

Experiments and Results Extreme Fast ( = 1) Ff = 55.0 Fs= 285.5 1500 iterations - 50 ants Extreme Safe ( = 0) Ff = 80.5 Fs= 7.3 EXAMPLE MAP. extreme-hCHAC-CSTR RESULTS

Experiments and Results Extreme Fast ( = 1) Ff = 57.5 Fs= 375.6 1500 iterations - 50 ants Extreme Safe ( = 0) Ff = 93.0 Fs= 8.4 EXAMPLE MAP. extreme-hCHAC-DSTR RESULTS

Experiments and Results Fastest ( = 0.9) Ff = 75.0 Fs= 306.0 1500 iterations - 50 ants Safest ( = 0.1) Ff = 88.50 Fs= 8.1 EXAMPLE MAP. MOACS RESULTS

Experiments and Results Ff = 78.0 Fs= 7.5 1500 iterations - 50 ants EXAMPLE MAP. mono-hCHAC RESULTS

Conclusions and Future Work We have solved a military pathfinding problem, taking into account realistic properties and restrictions. We have implemented and tested a MOACO algorithm with some configurations and using different state transition rules. We have compared it with an extreme, a good famous algorithm (adapted to the problem), and a mono-objective approaches. The hCHAC algorithm presents better results considering the choosed compromise between objectives. Future Work : Compare the algorithm with other pathfinding methods. Implement a dynamic approach. Include time restrictions and partial solutions.

We have solved a military pathfinding problem, taking into account realistic properties and restrictions.

We have implemented and tested a MOACO algorithm with some configurations and using different state transition rules. We have compared it with an extreme, a good famous algorithm (adapted to the problem), and a mono-objective approaches.

The hCHAC algorithm presents better results considering the choosed compromise between objectives.

Future Work :

Compare the algorithm with other pathfinding methods.

Implement a dynamic approach.

Include time restrictions and partial solutions.

Thank You !!

## Add a comment