A smart way to adjust XML files according to handwritten ones

Question

I have a game application with characters that have to cross mazes. The game can generate thousands of different mazes and the characters can move according to users choice and cross the maze manually. We needed to add the possibility to show a correct way out of each maze. Therefore we added the possiblity to move the characters according to an xml file.

This XML file is very complex, usually around thirty-fifty thousands of rows. lets say its in the following structure (but much more complex):

  <maze-solution>
  <part id="1">
  <sector number="1">
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1250></start-position>
            <angle>23.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>run</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>light</equipemnt>
        <movement>
            <start-position>4223></start-position>
            <angle>233.43</angle>
            <duration>0.32</duration>
        </movement>
        <action-type>walk</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1231></start-position>
            <angle>84.134</angle>
            <duration>0.454</duration>
        </movement>
        <action-type>run</action-type>
        <character>2</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>932></start-position>
            <angle>34.43</angle>
            <duration>0.50</duration>
        </movement>
        <action-type>duck</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>   
  </sector>
  <sector number="2">
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1250></start-position>
            <angle>23.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>run</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>light</equipemnt>
        <movement>
            <start-position>4223></start-position>
            <angle>233.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>walk</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1231></start-position>
            <angle>84.134</angle>
            <duration>0.454</duration>
        </movement>
        <action-type>run</action-type>
        <character>2</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>932></start-position>
            <angle>23.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>duck</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>   
  </sector>
  <sector number="3">   
  </maze-solution>

At the moment, we have the ability to analayze each maze using a CNN algorithm for image classification and generate an xml that represents a way out of the maze - meaning that if the characters will be moved according to that file, they will cross the maze. That algorithm has been tested and can not be changed by any means.

The problem is that most of the times the generated file is not the best one possible (and quite often it is very noticeable). There are different, faster, better ways to cross the maze.

We also have thousands (and we can get as many as needed) files that were created manually for saved mazes and therefore they are representing an elegant and a fast way out of the maze. The ideal goal is that someday, our program will learn how to generate such a file without people creating them manually.

To conclude, we have plenty of XML files generated by a program compared to the hard-coded XML files. There are thousands of pairs - The file the program generated, and the "ideal" file version that a person created. (and we can get infinite number of such pairs) Is there a way, using those thousands of pairs, to make a second step algorithm that will "learn" what adjustments should be made in the generated XML files to make them more like the hard-coded ones?

I'm not looking for a specific solution here but for a general idea that will get me going. I hope i made myself clear but if I missed some info let me know and I will add it.

Answer 1

So I see two parts to your problem where machine learning is appropriate.

1. Generating a maze solution or set of possible working solutions
2. Selecting/optimizing the best solution from part 1 above

Seems like part 1 is already addressed by you so I will share some suggestions on part 2 to explore.

If you can parse the XML file to extract elements and express them as a sequence of directions (like way old school turtle programming language) --

light, go forward 10, move 10, pick up, stop, drop, turn 10

...... then you can use the seq2seq machine learning technique to train a neural network to take semi-optimized sequences and find the the best sequence.

In other words, the seq2seq NN will be trained on pairs of sequences that consist of a non-optimal sequence and a corresponding "ideal" sequence. This is similar to neural machine translation and summarization but you are translating sequences. NN architectures that apply in this case are RNN, LSTM, etc.

Hopefully this gets you started with some exploration. I don't have personal experience with using seq2seq in this domain but this seems appropriate.