#625 Player: Offline path computations with wavefront

Player (393)

The attached patch adds offline path computation capabilities to wavefront, i.e. allows one to calculate waypoints for a path without executing it and without affecting the path wavefront is currently following. Besides, it calculates the total path length both for offline computed paths and for the current path. (Both features were listed as TODOs in wavefront.cc for a long time already, and I needed them for optimal tour planning.)
The patch is based on work from a fellow student, Paul Neugebauer, who kindly permitted me to submit it.

To realize this, the planner interface is extended by a new request GET_OFFLINE_WAYPOINTS and a corresponding struct player_planner_offline_waypoints_req containing a start pose, goal pose, total path length, number of waypoints and the actual waypoints. The existing player_planner_waypoints_req is extended by a total path length field as well.
Wavefront, the only driver providing the planner interface, is extended as follows: The Wavefront class gets a new member offline_plan for calculating paths independent of the current plan. offline_plan is created as a copy of the current planner (to avoid the costly recomputation of the C-Space map) when a GET_OFFLINE_WAYPOINTS request comes in and it has not been created yet. When the map (and thus the normal planner) changes, offline_plan is deleted so it will be recreated as a new copy of the updated plan when needed. This way the new feature does not incur any overhead when it is not used, and the overhead of the second planner is kept to a minimum. Both for GET_OFFLINE_WAYPOINTS and GET_WAYPOINTS requests, wavefront calculates the total path length as the sum of euclidean distances between the waypoints on-the-fly while copying the waypoints to the response struct.
As a bonus, the patch removes the two TODOs from wavefront.cc :)

Alternatives: player_planner_waypoints_req already contains everything one needs as a response to a GET_OFFLINE_WAYPOINTS request, so it seems it would make sense to reuse it for that purpose. However, the way libplayerc is implemented, the response must use the same struct type as the request. One could change client_libs/libplayerc/client.c accordingly to allow different struct types for request and reply, or one could use the player_planner_waypoints_req to also convey the request (by setting start and goal as two waypoints in the struct), but I think the chosen solution is the lesser evil.

Shortcomings: wavefront has a force_map_refresh setting which fetches a new map and updates the planner whenever a new goal comes in. For offline path computation requests, the force_map_refresh setting is currently ignored. (The offline planner will be updated whenever the main planner got updated, but it never gets updated on its own.)

The patch is against Player-3.1.0-svn revision 8914.


  • Rich Mattes

    Rich Mattes - 2010-11-12

    I don't know if we need to add a whole separate message to the interface, especially since it's essentially a copy of one already available. What if, instead, wavefront was changed to provide 2 planner interfaces, something like

    provides ["online:::planner:0" "offline:::planner:1"]

    This way, you can query planner:1 for waypoints that you want calculated offline, and planner:0 still acts as it always did. And if there's no provides for an offline:::planner in the configuration file, the offline planning isn't enabled. Do you think this is an acceptible solution?

  • Jan Schlüter

    Jan Schlüter - 2010-11-12

    Nice idea, I didn't think of this solution. This would probably be better than duplicating the waypoints message. The planner interface should still be extended to include the total path length in GET_WAYPOINTS, but we don't need a new message then.
    But would this break existing configuration files? Would people always need to specify "online:::planner:0" even if they do not use the offline planner, or could you still have wavefront accept an unnamed "planner:0" interface?

    Unfortunately I will not be able to implement your suggested solution anytime soon, as my work on the university project using Player is finished and I am working on a totally unrelated project now. However, I will point my colleague to this tracker.

  • Rich Mattes

    Rich Mattes - 2010-11-12

    The double interface scheme could be implemented in a way that won't break existing configuration files: the driver could first check for an interface with the "online" key, and if it doesn't find one it can fall back to looking for an interface without a key.

    I agree with the idea of adding the waypoint path length to the interface, that seems like quite a useful piece of information to be receiving.

  • Rich Mattes

    Rich Mattes - 2013-11-11
    • assigned_to: Brian Gerkey --> nobody
    • Group: --> Release-3.1
  • Rich Mattes

    Rich Mattes - 2014-02-16
    • assigned_to: Rich Mattes
  • Rich Mattes

    Rich Mattes - 2014-02-18
    • status: open --> pending
  • Rich Mattes

    Rich Mattes - 2014-02-18

    I finally got around to doing this. The way I implemented it was as follows:

    Added a message (CMD_START) to the planner interface, to optionally set the start position for the planner. This could see more general use if you want to plan between two arbitrary points, and not necessarialy start your plan where your robot is

    Added the waypoint distance to the waypoint list request as you did.

    Made the wavefront driver provide two planner interfaces: one with a blank tag, and one with the "offline" tag. The "offline" interface accepts start and goal commands, and plans a new path when you request waypoints. The online planner works as it did before.

    Changes committed as r9139 and r9140, let me know if there are any issues.


Log in to post a comment.