elsopuro / ahastar Goto Github PK

The performance of OHA* depends on the effectiveness of the map
decomposition. If large empty rectangles can be identified we expand much
fewer nodes and obtain bigger savings (vs. A*) than if small rectangles are
found.

In that spirit, we need an algorithm for decomposing a grid map which
yields optimal size rectangles. One obvious method is to use a backtracking
search where the root has as a successor each traversable tile on the map.
Each node is the origin of some empty rectangle. We select for expansion
the one that allows the largest rectangle to be built. 
This is a systematic search that guarantees an optimal solution is found.
In particular, the optimal solution is the one where each traversable tile
is assigned to a rectangle and the total number of rectangles is minimised.

We might be able to speed things up by using a branch-and-bound approach
where a lowerbound is computed for each rectangle. 
One lowerbound is to relax the problem and take the maximum size of the
rectangle that can be built if we ignore horizontal obstacles and then
veritcal obstacles.

When using EmptyClusterAbstraction, if the S+G are in the same cluster, we can 
return a path without search. At the moment however we need to insert both and 
search inside the cluster.

Inserting and removing start and goal nodes into the abstract graph is 
currently the responsibility 
of HPAClusterAbstraction. This is a legacy design that needs to be changed. 

Inserting is a pre-processing step we perform before running a search on the 
abstract graph so it 
should be dealt with by the class implementing HPA`*`

HOG's AStar hierarchy is a mess. Lots of re-implementations, no shared code
etc. Need an abstract parent implementing things like
edge relaxation, path extraction and drawing paths(maybe).

Currently, ClusterAStar may be limited to running inside a single cluster by 
evaluating the 
parentClusterId attribute of each node prior to expansion.

It would be nice if instead -- or in addition to the current functionality -- 
it could take a set of 
nodes as the "cluster" inside which search is limited. 
If we replace the existing clusterId approach it would also remove the 
requirement that only graphs 
composed of ClusterNodes may be used which would make it a much more general 
search 
algorithm for HOG.

Currently, AnnotatedHierarchicalAbstraction and AnnotatedAstar both rely on 
precomputed 
clearance values annotated directly into the node class. This is an old legacy 
design. 

It would be much better if the getClearance method of the node being evaluated 
would perform 
this calculation directly. This would bring the design closer to what is 
outlined in the paper.

Currently, the software assumes only 2 terrains per map (ground and trees). 
AMA should be generalised to calculate clearance for any HOG-supported terrain 
type.

Only one exists at the moment -- AHAScenarioManager which deals with
capabilities and sizes etc. 
We need a more generic one that doesn't rely on nodes being annotated with
clearance info.

HOG is GPL and HAA et al extend it. Thus they are also GPL.
However, most new source files don't contain the license headers (they should).

Agents can either be small (1 tile) or large (4) tiles. It would be nice to 
allow agents of arbitrary 
user-specified size to traverse the map.

Often it is useful to swap one kind of Map object for another.
For example, sometimes we want to build an octile grid while other times a
4-connected tile grid suffices.

There's no easy way to achieve this at the moment.
This issue should probably be fixed using a factory-based approach.

In results, replace zigzag effect stuff with a better explanation. Large agents 
have no single terrain 
transitions to choose from; forced to use the single transition point in the 
cluster which can be 
quite suboptimal. 

In intro, replace Red Alert & Total Annihilation with Company of Heroes and 
Dawn of War II?

EmptyCluster and EmptyClusterAbstraction only connect adjacent clusters
using horizontal or veritcal edges. To extend OHA* to the 8-connected case
we need to consider diagonal transitions too.

When identifying entrances:
 - Every node in the entrance area must appear in the abstract graph
 - Every edge connecting a node to another node in a different cluster must 
   appear in the abstract graph. 

What steps will reproduce the problem?
1. Download copy of project.
2. Run in Xcode.
3. Fails due to missing libraries-> (libcppunit.a and libmockpp.a)

What is the expected output? What do you see instead?



What version of the product are you using? On what operating system?

Mac osx

Please provide any additional information below.

:(

OHA* builds a new graph based on a given octile map.
This means we have additional storage overheads.

Instead, we should be able to directly prune the original graph
and simply insert macro edges instead.

Searching on this sparse graph will involve inserting the start or goal.
We'll need to keep a complete matrix of cells with cluster ids to do this
but each id is much cheaper to store than the associated node that 
we delete.

NB: there is still some overhead; notably, we need to store cluster ids
even for the nodes that we do not prune.

In the worst case, we cannot build any rectangles with interior nodes and 
we store an additional identifier for each cell. 

All units are shown as small single-size agents occupying one tile. 
We should visualise larger agents properly and have them occupy the correct the 
number of tiles 
when running a simulation in GUI mode.

This means fixing CapabilityUnit to draw agents correctly and searchUnit in 
favour of it in 
runNextExperiment (sample.cpp) with it when finished.

There is a small bug in the AnnotatedHierarchicalAStar when the start and goal 
are in the same 
cluster. 

If the low level search to find a direct path inside the cluster fails, the 
search effort for that single-
cluster search is clobbered when the abstract path is computed (search metrics 
are reset when 
getPath is called).

Node expansion for OHA* on 8-connected grid maps is somewhat different to the
4-connected case. Specifically:

0. Every node has an (initially undefined) macro parent.
1. Need to mark each node that enters a new cluster (from another cluster).
2. Every node n entering a cluster has a macro successor ms. Each successor
of ms, designated n', is evaluated with respect to n by way of Pythagoras'
theorem.
3. Relaxing nodes on the open list involves updating their macro parent
if a shorter path has been found.

To implement (2) use square distances (sqrt operation is expensive):
dist(n, n')^2 = dist(n, ms)^2 + dist(ms, n')^2

To implement (3) need to override aStarOld::relaxEdge.

Furthermore, a new implementation of aStarOld::extractBestPath is required
to return the final path (we can't use the old one as that relies on all
nodes on the path being connected by an edge in the graph. The above will
require tracing from the macro parent of the goal backward to a node which
has the start location as its macro parent).

There is no nice way to see what edges/nodes are in a graph. This is useful for 
debugging.
This functionality is ideally added to HOG's graph class but may also be 
implemented in one of the 
abstraction classes -- usually, only the abstract graph needs inspecting.

A proof is required for the paper.
Can probably use a constructive approach similar to the 4-connected case but
outlining how the macro parent updates affect things.

this script has no inbuilt help and takes no parameters.
both issues need to be fixed.

Currently, the default node class is prevalent throughout the code. 
In particular, it is hardcoded into the the map class, the graph class. This 
makes it very hard to 
subtype node. 

We should refactor these classes to take a NodeFactory constructor argument and 
build all nodes 
from the factory. This will allow us to extend node in different ways (for 
example, an 
AnnotatedNode for HAA* and possibly others).

Currently, EmptyCluster overrides functionality it inherits from HPACluster
but does not require (eg ::connectParent). It also inherits attributes not
required (eg. ClusterAStar). 

The functionality common to both needs to be moved into an AbstractCluster
class which both inherit from. 

A similar story exists for the various ClusterAbstraction classes.

NB: also make sure each new implementation uses covariant return types so
we don't have to cast stuff all the time.

Search algorithms sometimes require more than a start/goal position 
to initialise. e.g. HAA* needs size and clearance.

Thus, it would be nice if we could just pass an Experiment object to the 
program and have it initialise from that.

Lots of unit tests refer to map files at fixed locations in the filesystem; eg: 
/Users/... etc
This makes the tests non-portable. These paths need to be made relative to the 
project.

A theoretical analysis of how many symmetric paths we break would be nice.

AbstractScenarioManager::generateExperiments takes as an argument an object of 
type 
AbstractAnnotatedMapAbstraction. This isn't very extensible. 

For the IA* work we need to refactor this method to accept a parameter of the 
more general 
graphAbstraction class. Specific concrete implementationg of 
AbstractScenarioManager (like 
AHAScenarioManager) which require a specific subtype of graphAbstraction can do 
a dynamic cast 
to check if the argument is of the right type.

We add some unnecessary macro edges at the moment (mostly to tiles in the 
corners of the room which are dominated by paths involving shortcut edges).

2 possible solutions arise:
 (1) hardcode some checks to make sure the code behaves correctly in these situations 
 (2) implement a method to find a path in the existing graph between the endpoints of the proposed edge; only add the new edge if the length of the path is strictly larger than the weight of the edge.

Hardcoded to aStarOld atm; not very flexible.

hogrunner, sample et al currently initialise an OpenGL window even when
running without a GUI. This makes it difficult to run the program in the
background. 

Instead, all OpenGL initialisation should be skipped when running with
"-gui disable".

Currently it is possible to create a new cluster with its origin inside
another cluster. This is wrong but there is no check at constructor time
because the ctor doesn't have a *ClusterAbstraction paramater.

Add this argument to the constructor, implement the new check and its
corresponding test, and remove *ClusterAbstraction as a parameter from the
signature of any functions in HPACluster/EmptyCluster.

Currently, AA* relies on each map tile being annotated with clearance values. 
This requires that all 
annotations are stored in memory at all times and the associated overhead is 
significant.

A better method would be if each agent computes clearances individually for its 
own capability as 
per Algorithm 1 in the paper.

Related: Issue 11

InsertionPolicy objects are currently passed to HierarchicalSearch. It would be 
better if these objects were passed as ctor arguments to the mapAbstraction in 
question. Then we could more easily check if the insertion policy is compatible 
with the abstraction.

Related to this: HierarchicalSearch should only insert by calling 
mapAbstraction::addNode

The current heap class breaks ties in favour of the parent node.
It should break them based on largest g-cost.

To support this a new heap class is required which takes a Heuristic template 
(or ctor parameter). 

The '@' terrain type found in many maps represents an obstacle. 
The default behaviour of the Map class is to not create a node for tiles of 
this type. 

This behaviour causes HAA* to crash in several places:
 - AMA::annotateMap
 - AAStar::evaluate

probably others too. 
The code currently deals with this by converting '@' terrain into water tiles 
which do have nodes 
associated with them (in Map::loadOctile). 

This needs to be fixed. HAA* should work given a default non-modified Map class.

Most implementations of INodeFactory and IEdgeFactory are almost
identical -- except for the types they operate on (eg. NodeFactory and
MacroNodeFactory to name a couple)

It would be nicer if, instead of creating a new factory every time a new
node/edge type is introduced, we could simply use a templated implementation.

More specialised factory types can simply extend INodeFactory (or the
proposed templated implementation) as required.