Page 1 of 1

Using matrices to implement a search algorithm in ExtendSim

Posted: Tue Jul 23, 2019 12:54 pm
by matt_aylward
1. I have a search problem that can be handled with matrices and dynamic programming, but am unsure how I to implement it in ExtendSim.

2. Here's the problem:
a. I'm simulating a large airfield (say, 300 feet wide and 10,000 feet long)
b. Periodically, holes of varying size appear in my airfield at random locations
c. Now, my airplanes only need a small patch of concrete (SPC) to takeoff and land (say 30 feet by 750 feet)
d. My simulation makes these holes appear in an acceptable fashion, but now I need to check if the required SPC exists after a hole appears.

3. I sketched out the code to check for SPC using geometry, but think that the number of required checks will become unwieldy, and I'd probably miss a few cases. Which made me think about using matrices. A Google search led me two sources:

a. This short video on YouTube: https://www.youtube.com/watch?v=g8bSdXCG-lA

b. This article describing a similar approach: https://www.geeksforgeeks.org/maximum-s ... matrix-1s/

4. If I put a Cartesian grid over the whole airfield, so that its area was subdivided into 10'x10' cells, I could then enter a '1' in a given cell if its surface is undamaged, and a '0' if its surface is damaged (NB: the ExtendSim model can readily tell me if a '1' or a 0' should go in the cell). Then the search algorithm could be invoked to find the largest contiguous SPC

5. Any tips/suggestions/examples of how to use matrices in ExtendSim will be much appreciated.

Re: Using matrices to implement a search algorithm in ExtendSim

Posted: Tue Jul 30, 2019 6:03 am
by davek
Matt,

I think your problem is a little different than the one in the algorithm. I believe its theoretically possible that the largest area would not have sufficient length for an aircraft, but a smaller area would be long enough. For example you could have one open patch that is 300 x 700 ft and another that is 40 x 750. As I understand it, the algorithm would find the larger, but too short area. You do have an advantage here in that the runway is not wide enough for aircraft so you will only have to search in one direction. I think you could use a similar technique to the algorithm but only have to search in one direction, looking through the columns of the array to determine the best area to use. You can store the status of the runway in a database table, global array, or dynamic array. The dynamic array would be the fastest (by far... you could even use a C++ DLL to find the area which would speed it up even more), but the database provides better visualization possibilities. Doug Shannon from the Aerospace Corporation has developed a Heat Map block that would effectively visualize the runway if you used a database table.

We have some ideas here about how to approach this. Please feel free to contact me here at Kromite if you want to discuss this.

Dave Krahl
Kromite LLC
www.kromite.com

Re: Using matrices to implement a search algorithm in ExtendSim

Posted: Tue Jul 30, 2019 6:03 am
by davek
Matt,

I think your problem is a little different than the one in the algorithm. I believe its theoretically possible that the largest area would not have sufficient length for an aircraft, but a smaller area would be long enough. For example you could have one open patch that is 300 x 700 ft and another that is 40 x 750. As I understand it, the algorithm would find the larger, but too short area. You do have an advantage here in that the runway is not wide enough for aircraft so you will only have to search in one direction. I think you could use a similar technique to the algorithm but only have to search in one direction, looking through the columns of the array to determine the best area to use. You can store the status of the runway in a database table, global array, or dynamic array. The dynamic array would be the fastest (by far... you could even use a C++ DLL to find the area which would speed it up even more), but the database provides better visualization possibilities. Doug Shannon from the Aerospace Corporation has developed a Heat Map block that would effectively visualize the runway if you used a database table.

We have some ideas here about how to approach this. Please feel free to contact me here at Kromite if you want to discuss this.

Dave Krahl
Kromite LLC
www.kromite.com

Re: Using matrices to implement a search algorithm in ExtendSim

Posted: Wed Jul 31, 2019 12:51 pm
by matt_aylward
Dave,

1. Thank you for the very helpful reply. I had only given the algorithm a cursory check, and did not realize that returning the largest rectangle might not answer my information requirement. Probably I was grasping at straws.

2. After posting my original question, and following a few more sleepless nights, I realized that my mental model of the problem was creating most of the trouble. Once it dawned on me that I should divide the runway into strips of the required width and length, then the does-a-SPC-exist check becomes much easier.

3. Still haven't worked out all the logic checks yet (just finished cutting out strips of cardboard to represent the larger runway that holds some number of SPC); but am feeling more hopeful. And yes, keeping track of the runway sections in a table seems like the best way to go.

4. I think a table to keep track of the holes is needed as well, since they come and go according to their own rhythm and processes.

5. Probably won't get a working prototype together before next week's vacation, but will post the model once it's running.

6. Am intrigued by your comments re Aerospace Corporation and a Heat Map block; will get guidance from my management before taking any more of your time.

Re: Using matrices to implement a search algorithm in ExtendSim

Posted: Thu Aug 15, 2019 10:39 am
by matt_aylward
Dave, and anyone else on the forum,

1. We're still working on determining if the SPC (small patch of concrete) exists when a crater appears in the larger runway.

2. Two other analysts at work came up with some Python pseudo-code for determining if a SPC exists.

3. Which leads to questions about how to link ExtendSim to the Python script. ExtendSim needs to tell Python about the craters (e.g., when they appear, where they appear, how big they are, when repairs are complete), and Python needs to tell ExtendSim if a SPC exists (and possibly where it exists).

4. A few months ago, someone posted a related query to the Python user forum https://python-forum.io/Thread-Embeddin ... simulator . Fortuitously, they were asking about embedding Python in ExtendSim. I don't know if they succeeded in their efforts, or if they cross-posted their query to this forum.

Re: Using matrices to implement a search algorithm in ExtendSim

Posted: Sun Aug 18, 2019 4:37 pm
by davek
Matt,

We have both Python and ExtendSim programming expertise here at Kromite. The easiest way to do this is to write the array to a file, call WinShellExecute to run the Python program, and then read the data back into ExtendSim. If this is not fast enough then you can either figure out a way to call Python from a COM interface, wrap the Python code in a DLL, or port the Python code to ExtendSim.

Dave