shaybarak / hqmp Goto Github PK

When getting the additional targets, currently we are just trying to add layers of thier rotation and connectors on point. this is not well enough.
Idea:

1. Check if current handling is enough to connect targets.
2. If additional targets are not connected:
   If the graph was well connected before, that means that new ocnnectivity components were added. In this case we need to connect the new connectivity components to the graph.
   From first glance, it appears that "create_connecting_points indeed should take care of the situation.

Thanks for commit 4bb269b but you deleted an important feature for testing and experimentation.
Please fix it.

Else we give second player the advantage, wasting half turn in planning!!
If we are the first, try to run heavy computations on second turn, not on the first

@shaybarak comment whatever ...

Run regular scenario(2 MYPlayers, release mode) and observe.

i.e. maybe set default parameters, if not given?
According to Oren, we can specify additional parameters in configuration file, this requires error handling whatsoever

Reference points will be sampled such that their locations will be covered as intersections and their rotations will be sampled as layers.

Then we can pass the source point and all (initial) target points to preprocessing.

There is a bug that causes an access violation in follow_polygon_edges. It's most likely in the loop that begins at ShortestPathInPolygon.h:238, though I'm not sure because the stack trace in Release is not accurate. The bug could be either in the loop's body or in the exit condition.

This crashes the player and causes us to lose the match.

To recreate the crash:
Run the simplest scenario, under Input. It's the standard maze with both players and all three targets outside the maze.
Player B crashes.

Please:

1. Test your code against more than one scenario!
2. Either fix this by the end of the day or revert back to Oren's code.

@yasminsl
@idansayag

When we receive additional targets, we should take the time to add these targets to the preprocessing.
This means that we should expose an additional_preprocessing method that takes additional points and updates the preprocessed data.

Find dominating parameters for best quality vs. runtime tradeoff.
Identify improvements and implement them.

bool can_connect_to_targets(Ref_pt& source, Ref_p_vec& targets)

This is a MUST for the documentation & presentation.

If the other player hasn't moved between calls to our move method, then there's no point in re-copying the planner.

The technical meaning (all variables and methods in the following appears in MyPlanner.h):
If this parameter is specified, method "filter_out" will take action, right after new connector is generated, and before it is added to _lines.
A connector is being filtered if it does not connect any connected "connected componenets" (or connect only componenets there are already connected).
Generally, it means we might need to plan some longer path within polygon untill we reach the connector constarint (the fixed point).
On the other hand:

1. We spare some preprocessing time.
2. The layers connectivity graph is smaller (but I am not certain it matters to any graph algorithm...?!?)

Unhandled exception at 0x00ac82aa in client.exe: 0xC0000005: Access violation reading location 0xfffffffc.

Need to figure out a strategy - either fix all invalid steps or reconstruct from scratch.

In order to validate a step we introduce the dynamic obstacle into each configuration space, after it's been expanded according to our robot's polygon (via Minkowsky sums).
It's faster if we just cache the expanded dynamic obstacle and simply rotate and translate it upon every validation before inserting it into the relevant configuration space.
This is an enhancement. I haven't measured the impact of this improvement yet.

Actually we can, examining size of some member of lines, however it is bad practice i think

In order to spare some time of computation:
Compute "Aerial distance" and "Aerial time" (including rotation), if this time is higher than best time, go to next point.

There aren't supposed to be any unbounded FSCs (polygons with holes such that there is no boundary - the polygon is the entire space except perhaps for a finite list of finite holes).
However, it appears that we've been hit by a bug in CGAL. Consider the following scenario:

Polygon_set free_space = ...
free_space.complement();
free_space.complement();

You'd expect that complementing a polygon set twice will have no effect, but it actually introduces another polygon that has the boundary as a hole and is otherwise unbounded.
This causes a crash later on, when we try to find the bounding box of two polygons which are unbounded. They pass the intersection test (naturally...) but crash on bbox construction - because they are unbounded.

Instead of fixing CGAL we introduced a workaround that skips unbounded polygons in the method that attempts to improve connectivity.
We are testing this fix now. So far so good.

Refactor planner's preprocess method to allow additional preprocessing mid-game.
Then leverage this functionality in the player logic.

Asuumption:
All targets are reachable (except for blocking from the other robot)!
Therfore if no path found (before the invalidation), must search deeper!

See in_maze_scenarion

Currently we are assuming every point returned from generate_random_point_in_polygons(fsc_1->polygon, fsc_2->polygon) will yield to a connector between fsc_1 and fsc_2, but it might be that no interval exist between this 2 fsc's!

see Oren thesis, paper.
This could be hard, and we might need some advices.
However if we implement this, i expect this to be a knockout!

@idansayag : call me for any questions

see https://github.com/shaybarak/HQMP/blob/master/workshop_beta/Graph/Graph.h : 112

We assume that every motion sequence that is returned from the player is executed.
This is not necessarily the case.
We need to handle failures correctly and roll-back failed movement attempts. Making a false assumption will cause all subsequent motion to be incorrect.

A corner case where one of the angles is +-180 degrees causes the planner to make the correct decision about the correct direction to turn in only 50% of the cases.
This is because of the way that Oren's rotational parameterization works, and his handling of unbounded intervals.

I can add some term in the function, but i think caller should take care of it?

@idansayag : please see if you can handle this issue till tuesday as well... call me for some explanations:)
@yasminsl : please see if you can handle this issue till tuesday as well... call me for some explanations:)

Method call:
https://github.com/shaybarak/HQMP/blob/master/workshop_beta/Planner/MyPlanner.h#L182

Method definition:
https://github.com/shaybarak/HQMP/blob/master/workshop_beta/Graph/Graph.h#L112
(need to change dijkstra implementation/parameters).

some heuristic could be:
In polygon: distance between the 2 relevant vertices(closest to target and source) * 1.4 / translational_speed
In Interval: angle between 2 edges of the interval / rotational_speed

Convex polygons are easy.
In other cases may want to triangulate.
In some cases it may be beneficial to follow the edges of the polygon.

Having the following assumptions:

1. Source, targets, and all aditional targets are sampled with both connectors and layers.
2. Every motion_step is inside fsc's and therfore every point in a motion step belongs to a node(or an edge?) in the graph.

Thus, connect to graph should do nothing, and in myplanner::query", perturbed_source == source, perturbed_target==target.
Should add an assertion/log message when connect_to_graph does return differnt points.

At the beginning of the game, first connect all target configurations to the graph.
Afterwards, when the additional points were added, connect all additionals to the graph as well (this requires an interface change for Player).
This will not slow us down because we have to connect each target to the graph at some point anyway.
This has the advantage that we'll be able to remove the call to connect_to_graph from query and query_closest_point (because we can safely assume that all reference points of interest are already connected). Currently we call connect_to_graph multiple times on points that are already connected starting from the second call to query_closest_point - this is somewhat wasteful, though I'm not sure how bad this is (does anyone have any numbers for how long it takes to do connect_to_graph when the point is already connected?).
Edge case to consider: when we cut a single motion step in two (movement part and remaining part) we need to remember to connect the interim reference point to the graph as well.