3
$\begingroup$

Given a virtual game map (picture) and a racing car at the map's starting point, I'm trying to build an algorithm that would help me generate a route that would get the car from the beginning to the endpoint.

route definition: a very complex .xml file that includes all the data the car needs in order to navigate the road successfully.

What I have:

  • I have thousands of different maps and I could get any number of maps I'd like.
  • For every map, I have a complex external algorithm using picture analysis that builds a route for me - although this route is not so accurate.
  • For some percentage of the maps, I also have a specific "good working car solution" - which is basically a manually built route file.

What I'm trying to achieve: Basically, I'm trying to improve the complex route generator algorithm which I don't have access to. I want to use the percentage of manual routes I have and compare them to the routes that are generated for the same maps. From the comparison and the differences between the manual and the automatically created route files, I want to build a second-step smart algorithm that "learns" what should be changed in the automatically generated routes and have that algorithm run as a second step and make it as close as possible to the handmade route.

My final goal is to be able to build an accurate route for maps I don't have the manual route for. I want to be able to produce an accurate route for every map - using both the external algorithm and the one I will build on top of it.

This entire subject is very new to me and I'd like to get your advice as to how should I approach this complex problem, and what could make this task easier for me.

$\endgroup$
0
$\begingroup$

Terminology

There are two uses of the word map in this discussion.

  • Road maps are construed below as images of road maps.
  • Mapping input to desired output is the skill the system must learn.

The set of examples used to teach the system from an existing mapping of input to output is called a labeled data set and the associated type of learning is called supervised.

Training Resources

  • Unreliable labeled road map examples and access to more also unreliable labeled road map examples
  • A large number of unlabeled road map examples and access to more road maps
  • A smaller number of labeled road map examples

Inputs

  • Virtual game map as an image
  • Starting position
  • Target ending position

Output

  • The fastest route in sufficient detail to fully direct car movement — Assuming that the route should be optimized for soonest arrival time, not for fuel conservation, minimal tire wear, safety, or minimal distance, since the car was identified as a race car.

Accurate Valuation of the Resource Inventory

The low quality routes from the black box service provide neither examples of desired system behavior nor examples undesirable system behavior. The former case would be good training data. The later would be good to use in an adversarial architecture based on the design of GANs and their variants. The uncertain quality of the labeled data from the black box service makes it ambiguous and, from an information science point of view, of zero value.

Comparing the low quality routes and the high quality routes may be interesting, but not particularly useful given the current state of machine learning. The objective of your initial project phase is to teach the machine to generate a high quality route from the low quality route, not produce a comparison report. To do that without processing the images a substantially large overlap between these two sets would be required.

  • The smaller number of labeled road map examples for which the labels were created manually
  • Corresponding labeled road map examples for which the labels were created by the black box service

That approach would require you to correct bad routes to create a sufficient training set. Without overlap, you have no training data for artificial network training. It may be possible to create an algorithm of GAN style that learns how to correct the black box service output using a concept called cross-entropy, but it would require processing the images and would likely be more difficult to do so than to replace the black box service altogether.

If your ultimate goal is to create a working system that generates routes from images and start and and positions, I suggest discounting the external service altogether, and discard the idea of creating a route improver sub-system. That you wish to improve upon the black box route generator's algorithm is noble but ultimately a time-consuming distraction to reaching the ultimate goal.

Replace the unreliable thing with the reliable thing you design and build and to which you will have full and open access to improve. Your system will ultimately have to deal with the images in your code either way, and that's the most challenging aspect of the overall task. Just learn about CNNs and RNNs and get right to it. That's my advise anyway.

A Note on Feedback

For any non-trivial route, the car will not likely stay on the road if given only turn, acceleration, and deceleration instructions. Detection of the edges of the road would normally be needed as a feedback mechanism to accompany the route instructions. The only way around this is to make the visualization sufficiently accurate that cumulative errors never exceed the distance that would put the car off pavement.

A Note on Data Representation

JSON has a more flexible and terse structure when it comes to homogeneous arrays than XML, and it is easy to convert XML to JSON. Furthermore, a transportation route is often represented as a directed graph, and there are many algorithms already conceived in graph theory that have been implemented in graph libraries in most languages. For instance, shortest path, path equivalence, path concatenation, and detection of rings (driving in circles) are one line calls to these libraries. Because JSON, for the reason given, has overtaken XML in many domains, the number of graph libraries that can read and write JSON directly has overtaken the number that can read or write XML directly. The tooling for JSON analysis and visualization has surpassed that of XML at this point too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy