AddAutomaton simple Python example?

[Ben Griffin]

I’m looking for a simple sample/example of AddAutomaton. I’m not very familiar with FSM/FSA and a tiny example of how (and, ideally, when) to use this would be welcome.

[Ben Griffin]

So, for example, I added a maze solver https://github.com/MrBenGriffin/or-tools-fun - this uses a AddCircuit() to solve a 2D maze.

I know that tutorial automata often use maze crawlers  - but I am not really sure I understand how to convert the Crawler class into an automaton suitable for ORTools.

[hakank]

Here is a very simple example of AddAutomaton:  http://hakank,.org/or-tools/regular_automaton_sat.py

It decodes the regular expression "0*1{3}0+1{2}0+1{1}0*" (i.e. "111", "11", and "1" with zeros between each set of 1s, and perhaps 0s before and after).

The tricky part is to create the automaton (the transitions). Here is the automaton for the problem above (calculated via `make_transition_matrix`):

```

(0, 0, 0) # 0* start state

(0, 1, 1) # 1{3}

(1, 1, 2)

(2, 1, 3)

(3, 0, 4) # 0+

(4, 0, 4)

(4, 1, 5) # 1{2}

(5, 1, 6)

(6, 0, 7) # 0+

(7, 0, 7)

(7, 1, 8) # 1{1}

(8, 0, 9) # 0* accepting state

(9, 0, 9) # 0* accepting states

```

I recommend to first create a simple version of the automaton with the good old pen and paper first. :-)

(The model a translation of my MiniZinc style regular constraint version http://hakank.org/or_tools/regular_sat.py and I'm using this principle for creating the Nonogram problem instances (see http://hakank.org/or_tools and search for "nonogram"). I _might_ translate the nonogram solver and the instances to Automaton version.)

Hope this helps.

/Hakan

[hakank]

Sorry, the link should be http://hakank.org/or_tools/regular_automaton_sat.py

[hakank]

And here's the Nonogram solver using AddAutomaton (instead of my old MiniZinc regular decomposition): http://hakank.org/or_tools/nonogram_automaton_sat.py

On can use the same problem instances as for the old Nonogram solver since the only difference is how to calculate the states (which is the same as for the example in my earlier post) + using the AddAutomaton constraints . The old instances are at http://hakank.org/or_tools/  , the one named nonogram*.py (which are not the Nonogram solver programs themselves).

For the problems I tested, this is much faster than the old nonogram_table.py  model, which is expected since it use a built-in constraint. (I might tweak it a little more later on.)

Using AddAutomaton seems to be much easier than the MiniZinc regular style. That's great!

[Ben Griffin]

@hakank,

Brilliant - thanks so much for providing me with enough to work with.

On 27 Feb 2021, at 21:47, hakank <hak...@gmail.com> wrote:



--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/V4Zf9o73ynY/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/29cde591-2a44-4b7a-b481-a13f8cf2f54dn%40googlegroups.com.

[hakank]

Thanks, Ben.

Here's the comparison between using AddAutomaton and using a decomposition of regular constraint (using AddAllowedAssignments) with a timeout of 60s.

As expected, nonogram_automaton_sat.py (with AddAutomaton) is significantly faster (211s) with only one timeout (for nonogram_pbn_dom16), while the older nonogram_table_sat.py takes 731s with 10 timeouts.

```

Total time automaton: 211.350252s

Total time table : 731.020601s

Instance automaton table

-------------------------------------------------

nonogram_pbn_9_dom.py 0.872295 33.336652

nonogram_pbn_bucks.py 0.018069 0.101534

nonogram_pbn_cat.py 0.004519 0.055420

nonogram_pbn_dancer.py 0.000617 0.003696

nonogram_pbn_dicap.py 0.205826 2.761004

nonogram_pbn_dom02.py 0.000345 0.001544

nonogram_pbn_dom03.py 0.005926 0.006044

nonogram_pbn_dom04.py 0.013333 0.020526

nonogram_pbn_dom05.py 0.023874 0.541823

nonogram_pbn_dom06.py 0.049942 1.774315

nonogram_pbn_dom07.py 0.157121 3.850751

nonogram_pbn_dom08.py 0.347990 13.857369

nonogram_pbn_dom09.py 0.883812 32.550134

nonogram_pbn_dom10.py 1.845537 60.000000

nonogram_pbn_dom11.py 3.405786 60.000000

nonogram_pbn_dom12.py 7.220187 60.000000

nonogram_pbn_dom13.py 16.631230 60.000000

nonogram_pbn_dom14.py 26.751668 60.000000

nonogram_pbn_dom15.py 52.803318 60.000000

nonogram_pbn_dom16.py 60.000000 60.000000

nonogram_pbn_edge.py 0.019300 0.040042

nonogram_pbn_flag.py 0.094609 0.927118

nonogram_pbn_forever.py 0.206298 0.687371

nonogram_pbn_hot.py 4.814303 11.233480

nonogram_pbn_karate.py 0.489679 2.081963

nonogram_pbn_knot.py 0.017048 0.230616

nonogram_pbn_light.py 1.100033 3.172661

nonogram_pbn_lion.py 3.185270 60.000000

nonogram_pbn_m_and_m.py 3.263962 7.726016

nonogram_pbn_marley.py 15.528986 60.000000

nonogram_pbn_merka.py 0.376428 2.236737

nonogram_pbn_mum.py 0.362214 1.284934

nonogram_pbn_nature.py 3.852760 60.000000

nonogram_pbn_petro.py 0.822752 3.263342

nonogram_pbn_signed.py 5.254635 6.327349

nonogram_pbn_skid.py 0.003256 0.048350

nonogram_pbn_smoke.py 0.087726 0.188815

nonogram_pbn_swing.py 0.046900 0.562794

nonogram_pbn_tragic.py 0.582698 2.148200

```

The benchmark program is here: http://hakank.org/or_tools/run_nonogram_sat.py

I have also updated my GitHub repo with these - and some other - models/programs: https://github.com/hakank/hakank/tree/master/google_or_tools

Ben: thanks for inspiring me to look a little further into AddAutomaton!

/Hakan