AddAutomaton simple Python example?

714 views
Skip to first unread message

Ben Griffin

unread,
Feb 27, 2021, 6:27:42 AM2/27/21
to or-tools...@googlegroups.com
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

unread,
Feb 27, 2021, 11:14:56 AM2/27/21
to or-tools-discuss

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

unread,
Feb 27, 2021, 3:45:52 PM2/27/21
to or-tools-discuss
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

unread,
Feb 27, 2021, 3:47:13 PM2/27/21
to or-tools-discuss

hakank

unread,
Feb 27, 2021, 4:47:30 PM2/27/21
to or-tools-discuss
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

unread,
Feb 27, 2021, 5:26:10 PM2/27/21
to or-tools...@googlegroups.com
@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

unread,
Feb 28, 2021, 4:58:06 AM2/28/21
to or-tools-discuss
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
Reply all
Reply to author
Forward
0 new messages