Route Inspection of Directed Graph in ASP

Question

For the multidirected graph below I am trying to write an program that visits all edges at least once. For instance, in the below graph I am looking for an outcome similar to "edge(1,2), edge(2,3), edge(3,1), edge(1,2), edge(2,4), edge(4,5), edge(5,4), edge(4,3), edge(3,1)"

Here is my code so far. It does not run properly, but I do not know how to fix it.Could you please assist on how to continue? Any advice or code is welcome.

Basically, I believe I am looking for a variation of an Eulerian Cycle where the edges can be visited more than once.

edge(1,2). edge(2,3). edge(3,1).
edge(2,4). edge(4,3).
edge(4,5). edge(5,4).
    
#const s=1.
start(s).

time(1..20). % allow at most 20 time-steps

1 { move(edge(X,Y),step(T)) : edge(X,Y) } 1 :- time(T).

:- move(edge(X,Y),step(1)), edge(X,Y), X!=s. % start from s

:- move(edge(X,Y_1),step(T)), move(edge(Y_2,Y),step(TT)), TT=T+1, Y_1!=Y_2.

visited(X,Y,T) :- time(T),move(edge(X,Y),step(S)), S<T, T<=20.
visited(X,Y,T) :- time(T),move(edge(Y,X),step(S)), S<T, T<=20.

:- edge(X,Y), not visited(X,Y,20).

:- move(edge(X,Y),step(S)), S<=20, Y!=s. %ensures path is cycle (back to s)

#minimize { T : time(T) }. % here i try to get as many steps as possible out of the upper bound of 20 

#show move/2.

Answer 1

Your code has an issue in the line

1 { move(edge(X,Y),step(T)) : edge(X,Y) } 1 :- time(T).

Problem here is that you force a move on every timestep, meaning your path has to have 20 steps and which could be problematic for problem Instances where there is no solution for exactly 20 steps.

Additionally your line

:- move(edge(X,Y),step(S)), S<=20, Y!=s.

is a problem, since it forces every move to end in s - therefore the code is unsatisfiable.

Also are you searching for the minimum or the maximum? You code states minimum, your comment says maximum.

I altered your code a bit and now it seems to work. Main change is to introduce the number of steps taken and to remove the timer from the predicate visited.

#const s=1.
start(s).
1 {endt(1..20)} 1. % guess end time
time(1..T) :- endt(T). 

1 { move(edge(X,Y),step(T)) : edge(X,Y) } 1 :- time(T).

:- move(edge(X,Y),step(1)), edge(X,Y), X!=S, start(S). % start from s
:- move(edge(X,Y_1),step(T)), move(edge(Y_2,Y),step(T+1)), Y_1!=Y_2.
:- move(edge(X,Y),step(S)), edge(X,Y), Y!=s, endt(S). % end from s

visited(X,Y) :- move(edge(X,Y),step(_)).
visited(X,Y) :- move(edge(Y,X),step(_)).

:- edge(X,Y), not visited(X,Y). % visit all edges

#minimize { T : endt(T) }. 
#show move/2.

Output:

Answer: 1
move(edge(1,2),step(1)) move(edge(2,3),step(2)) move(edge(3,1),step(3)) move(edge(1,2),step(4)) move(edge(2,4),step(5)) move(edge(4,5),step(6)) move(edge(5,4),step(7)) move(edge(4,3),step(8)) move(edge(3,1),step(9))
Optimization: 9
OPTIMUM FOUND

for #maximize { T : endt(T) }.:

Answer: 1
move(edge(1,2),step(1)) move(edge(2,3),step(2)) move(edge(3,1),step(3)) move(edge(1,2),step(4)) move(edge(2,4),step(5)) move(edge(4,5),step(6)) move(edge(5,4),step(7)) move(edge(4,3),step(8)) move(edge(3,1),step(9))
Optimization: -9
Answer: 2
move(edge(1,2),step(1)) move(edge(2,3),step(2)) move(edge(3,1),step(3)) move(edge(1,2),step(4)) move(edge(2,4),step(5)) move(edge(4,5),step(6)) move(edge(5,4),step(7)) move(edge(4,5),step(8)) move(edge(5,4),step(9)) move(edge(4,5),step(10)) move(edge(5,4),step(11)) move(edge(4,5),step(12)) move(edge(5,4),step(13)) move(edge(4,5),step(14)) move(edge(5,4),step(15)) move(edge(4,3),step(16)) move(edge(3,1),step(17)) move(edge(1,2),step(18)) move(edge(2,3),step(19)) move(edge(3,1),step(20))
Optimization: -20