Forum: PogamutUT2004

Own A* (originally posted by BEvans)

I've been reading through all the tutorials and the Pogamut libraries and am hoping to be able to write my own AStar pathplanner so that the heuristic it uses to plan the path is defined by myself.

However i'm struggling to see how I could accomplish this. In Pogamut 2 where there was not a Pathplanner it seems to be simpler as it has its own AStar class which is used whereas the Pathplanner uses the native UT A*.

Does anyone have any advice on how I could go about doing this, if not I guess I will develop the bot in Pogamut 2.

Thanks
Hi BEvans!

It would be the best to avoid Pogamut 2 at all - Pogamut 3 is ready to provide the best for you.
May be, you are missing tutorial (we are currently working on) to show you modules (try to instantiate them in Pogamut 3 in prePrepareBot())
AgentInfo?
Players
Items
AdvancedLocomotion?
These will give you nice methods to play with.

AStar path planner is included inside P3 as well (though I would not claim it is totally bug free) - the version inside P3 is almost identical to P2 (copy paste ;). So there is no reason to switch to P2 if you need AStar.

Anyway - P3 is more bug free (note that P2 contains nifty bugs) and more importantly it is alive. P2 is more or less dead thing as we're all moving to P3. P3 also provides you with new cool features such as Map (double click on the running server) and GUI for POSH plan editor (create SPOSH bot and double click .lap file). We're going to cover POSH in a tutorial too.

Cheers!
Jakub
Hi, there are two implementations of PathPlanner interface, UTAstar and FloydWarshallPathPlanner. Maybe FloydWarshallPathPlanner is close to what you need. It can be a good starting point for you. If you have a look at 02-NavigationBot tutorial you will se how to instantiate this path planner correctly.
Rudolf

> I've been reading through all the tutorials and the Pogamut libraries and am hoping to be able to write my own AStar pathplanner so that the heuristic it uses to plan the path is defined by myself.
>
> However i'm struggling to see how I could accomplish this. In Pogamut 2 where there was not a Pathplanner it seems to be simpler as it has its own AStar class which is used whereas the Pathplanner uses the native UT A*.
>
> Does anyone have any advice on how I could go about doing this, if not I guess I will develop the bot in Pogamut 2.
>
> Thanks
I've been looking at the UTAstar code within the library, as well as the FloydMarshall, however after trying to implement the AStar class contained within cz.cuni.amis.utils.astar by modifying the FloydMarshall classes with the code in this AStar class i get countless errors.

Most of these errors relate to incompatible types, for example for computePath which I have in an AStarPathPlanner class I have :

AStarResult result = AStarPathPlanner.aStar(to, map, DistanceUtils.getNearest(navPoints, to), 10);

However due to the constructor for aStar needing the 'to' variable to be of type AStarGoal I am unable to do this as computePath needs 'to' to be of type ILocated.

Sorry for asking what must seem like stupid questions, and thanks.
Hi,
you will have to:
1) implement adapter class extending AStarGoal, AStarResult and AStarMap that will wrap the current navigation graph
2) pass these adapters into already existing AStar implementation
3) unwrap the result obtained through AStarResult class and return it from your implementation of AStartPathPlanner

The difficulties you are experiencing are caused by the fact that the AStar is implemented as a general algorithm that can be used in any search space, you will have to adapt this general implementation in order to use it for navigation.
I think that after reading javadoc for AStar you will be able to do this.
Let us know whether you succeeded.
R


> I've been reading through all the tutorials and the Pogamut libraries and am hoping to be able to write my own AStar pathplanner so that the heuristic it uses to plan the path is defined by myself.
>
> However i'm struggling to see how I could accomplish this. In Pogamut 2 where there was not a Pathplanner it seems to be simpler as it has its own AStar class which is used whereas the Pathplanner uses the native UT A*.
>
> Does anyone have any advice on how I could go about doing this, if not I guess I will develop the bot in Pogamut 2.
>
> Thanks
Additionally I may just do this by programming the whole thing from scratch and using the move along path commands and move to node commands to assist in this. However I have noticed that the NavPoint class has had the neighbouring nodes attribute removed from it so how would I go about retrieving the information of which nodes are the neighbours to a specific node?

Thanks
Check Navpoint.getOutgoingEdges() and NavPoint.getIncomingEdges().

Yes you can implement AStart from scratch, but I would suggest you to decompose path planning and path execution, Implement your own path planning but reuse existing PathExecutor since it can handle lifts (movers in UT terminology), obstacles etc. You will spend a lot of time reimplementing this functionality.
R
Thanks for the help so far.

I have been writing a wrapper for the AStarMap, however I keep getting the error that i am no over riding the getNodeNeighbours method when I am. I have pasted the code below, I am aware the get Edge costs etc need to be implemented properly.

public class AStarMapAdapt implements AStarMap{


/**
* Should return the distance from nodeFrom to nodeTo
* You can be sure that nodeTo is among the neighbours of nodeFrom.
* @param nodeFrom
* @param nodeTo
* @return cost of an edge
*/
public int getEdgeCost(NODE nodeFrom, NODE nodeTo)
{

return 0;
}


/**
* This should return a collection of nodes which are connected to this one.
*/
public Collection getNodeNeighbours(NODE node)
{
NavPoint nv = getNavPoint(node);
assert nv != null;

return (Collection) nv.getOutgoingEdges();
}

private NavPoint getNavPoint(Object node)
{

return (NavPoint) node;
/*else
if (node instanceof NeighNav){
return ((NeighNav) node).neighbour;
} else{
System.out.println("GameMapAStarMap.getNode(): wrong node type");
return null;
}*/
}


}
Just to add something else, is there anything similar in Pogamut 3 to the NeighNav class which was present in Pogamut 2?
maybe add template to the returned collection (I am just guessing):
public Collection getNodeNeighbours(NODE node)

NeighNav was transformed into NavPointNeighbourLink which is returned in map by NavPoint.getOutgoingEdges()
R
Thanks for all your help, I've been getting along with the programming fine, creating the wrappers for AStarMap etc., however I am still confused as to how I can obtain the niehgbours to a navPoint. The outGoingEdges function returns 2 parameters, so how would I turn these into a collection of NavPoints?

Thanks
Collection neighbours = new HashSet());
for(NavPointNeighbourLink link : navPoint.getOutgoingEdges().values()) {
neighbours.add(link.getToNavPoint())
}

however note that NavPointNeighbourLink contains information that should influence your path planning algorithm, read the Javadoc
R
I'm having problems with this still, when it comes to running the bot it gets constantly stuck on walls etc. I'm assuming this is due to the path being generated incorrectly. The code i'm using for computePath is ;

public PathHandle computePath(final ILocated to) throws PathNotConstructable
{

NavPoint toNavPoint = DistanceUtils.getNearest(navPoints, to);

AStarGoal goal = new AStarGoalAdapt(toNavPoint);
AStarMap aMap = new AStarMapAdapt();

NavPoint start = new NavPoint();


start = DistanceUtils.getNearest(bot.getWorldView().getAll(NavPoint.class).values(), bot);

getWorldView().getAllVisible(NavPoint.class);

AStarResult result = AStar.aStar(goal, aMap, start, -1);

List PathNavPoints = result.getPath();
List path = new ArrayList();

if (PathNavPoints != null)
{
path.addAll(navPoints);
}

path.add(to);

if (!result.success) return null;

return new AbstractPathHandle(path, true) {

public String getTargetDescription() {
return to.toString();
}
};
}

Hi,
there are multiple possible causes of getting stuck
1) the nearest navpoint can be behind the wall so you get stuck when going to it
2) not all neighbours of the navpoint are reachable simply by walking, sometimes you have to use teleport etc. unfortunately some of these situations aren't handled by the current SteeringExecutors

We are working on an extension that would be able to filter out all the edges that the bot fails to go through thus obtaining a navigation graph that you can reliably navigate on. You can read about it here http://diana.ms.mff.cuni.cz/pogamut_files/latest/doc/tutorials/ch05s04.html in section "Path planning".

R
btw. what SteeringExecutors are you using right now?
I'm using all the SteeringExecutors which are present in the link you provided. It shouldn't be a problem as it's only getting stuck on walls etc very rarely.

Thanks for all the help
If your AStar path planner is working you can contribute it to the repository so also others have an alternatiive to current two planners :-)
If you will put into a zip file somewhere on the web I will download it and commit it.
R