shaybarak / hqmp Goto Github PK
View Code? Open in Web Editor NEWHigh Quality Motion Planning for robots, TAU CS workshop 2012
Home Page: http://acg.cs.tau.ac.il/courses/workshop/spring-2012/high-quality-motion-planning-for-robots
High Quality Motion Planning for robots, TAU CS workshop 2012
Home Page: http://acg.cs.tau.ac.il/courses/workshop/spring-2012/high-quality-motion-planning-for-robots
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:
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:
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:
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
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:
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.