Date: Tue, 15 Feb 2000 From: Monica Nogueira To: Vladimir Lifschitz I have the following questions about section 3 of the paper: 1. Path of different robots don't intersect is represented by never occupied(N,XC,YC) && occupied(N1,XC,YC) && (N < N1). Any reason for (N < N1) instead of (N =/= N1)? Efficiency? 2. A robot never visits the same point twice, as: caused false if at(N,XC,YC) after occupied(N,XC,YC) && -at(N,XC,YC). Although you have a paragraph explaining the introduction of the last conjunctive term, I still can not grasp its meaning. Could you tell me the meaning of this rule in English? I don't know how to read it. In section 7, it's mentioned how inneficiently SATO performed compared to RELSAT. Did you have an explanation for that? I thought SATO was the search engine of choice before and had presented a better performance on other problems. Two other points are: a. Only now it hit me that in Ccalc (C language) time is intrinsically part of the language. It allows elegant constructs as caused occupied(N,XC,YC) after occupied(N,XC,YC). b. An example that occured to me is: imagine you have already a routing established for some circuit and there is a need for adding extra wiring without possibility of changing the existing ones. It seems that all you need to do, to represent the existing wiring in your program, is to add fluent occupied(N,XC,YC) in the initial situation for all necessary coordinates. Am I right? I like the paper very much. It presents the problem and its solution in a clear way. I think that representing the path (wire routing) as the trajectory of a robot, and using action languages to implement it is really a smart idea. =========== Date: Wed, 16 Feb 2000 From: Hudson Turner To: Vladimir Lifschitz The paper is lovely. I'll be sure to mention wire routing and combinational circuits with gate delays in my next funding applications. How much too small is "much too small"? A minor worry: If I understood, in approximate bus routing you relax the goal but keep the requirement that robots always move. Can this eliminate some solutions? Suppose wire 1 must have length between n and n+1, but the only such path is of length n, and there is no available unoccupied position for robot 1 at time n+1. Fun to wonder about how to make description smaller or otherwise easier to solve. ======== Date: Thu, 17 Feb 2000 From: Esra Erdem and Vladimir Lifschitz To: Monica Nogueira Thanks for your comments! Here are our answers to your questions: On Tue, 15 Feb 2000, Monica Nogueira wrote: > Dear Vladimir, > > I have the following questions about section 3 of the paper: > > 1. Path of different robots don't intersect is represented by > > never occupied(N,XC,YC) && occupied(N1,XC,YC) && (N < N1). > > Any reason for (N < N1) instead of (N =/= N1)? Efficiency? Yes, it is for efficiency. > 2. A robot never visits the same point twice, as: > > caused false if at(N,XC,YC) after occupied(N,XC,YC) && -at(N,XC,YC). > > Although you have a paragraph explaining the introduction of the > last conjunctive term, I still can not grasp its meaning. > Could you tell me the meaning of this rule in English? I don't know > how to read it. Here is how we could read it: a robot cannot arrive at a point (XC,YC) from another place if this point has been already visited by that robot. This proposition prevents a robot from re-visiting a point from another point. In this case, a robot is allowed to wait at a point. Without the last conjunct, a robot is prevented from arriving at a point (XC,YC) if this point has already been visited by that robot. In this case, a robot is not allowed to re-visit a point--including the one it is currently at. This prevents a robot from waiting at a point. Does this make sense? > In section 7, it's mentioned how inneficiently SATO performed > compared to RELSAT. Did you have an explanation for that? I thought > SATO was the search engine of choice before and had presented a > better performance on other problems. We don't know why relsat performs better than sato for the wire routing problems. We are surprised as well. But, we learned from Enrico that wire routing is not the only domain where relsat performs better than sato. > Two other points are: > > a. Only now it hit me that in Ccalc (C language) time is intrinsically > part of the language. It allows elegant constructs as > > caused occupied(N,XC,YC) after occupied(N,XC,YC). Right! When we use rules like h(F,T+1) :- occurs(A,T), causes(A,F,P), h(P,T). that has a similar effect: by writing rules for causes/3 we can talk about time without mentioning it explicitly, as if it were "intrinsically part of the language." What is really special about the example caused occupied(N,XC,YC) after occupied(N,XC,YC) is that this is a dynamic law that doesn't mention actions. The formalization of inertia in C is in the same category: caused F if F after F. > b. An example that occured to me is: imagine you have already a > routing established for some circuit and there is a need for > adding extra wiring without possibility of changing the existing > ones. It seems that all you need to do, to represent the > existing wiring in your program, is to add fluent occupied(N,XC,YC) > in the initial situation for all necessary coordinates. Am I right? It is a very interesting observation. Yes, you're right! ========= Date: Fri, 18 Feb 2000 From: Esra Erdem and Vladimir Lifschitz To: Hudson Turner Thank you for your comments. > How much too small is "much too small"? We are not sure, except that we know that there are two levels of success to be achieved by increasing the size of problems. One is to make examples respectable in the eyes of the computer scientists working in this area. The other is to make the method practically useful. > A minor worry: If I understood, in approximate bus routing you relax the > goal but keep the requirement that robots always move. Can this eliminate > some solutions? Suppose wire 1 must have length between n and n+1, but > the only such path is of length n, and there is no available unoccupied > position for robot 1 at time n+1. That's a good point. We'll work on the formalization of this problem to correct it.