Errata for 2dcaumsr.pdf A Two-Dimensional Crystalline Atomic Unit Modular Self-Reconfigurable Robot Marsette A. Vona, III BA Honors Thesis, Dartmouth College Department of Computer Science 1999 ----------- From: "Forrest Bennett" To: Subject: Your thesis Date: Wed, 31 May 2000 21:30:19 -0800 Dear Marsette Vona, I was reading through your thesis "A Two Dimensional Crystalline Atomic Unit Modular Self-reconfigurable Robot", and I have a question. In the pseudocode for Algorithm 2.2, the CalculateDisplacements() procedure is as follows: CalculateDisplacements(Crystal C, Dimension d) WHILE there exists an Atom m in C where m.action.d != null Axis x <- the d axis of m IF there exists an Atom a in x where a.segment != undefined CalculateAxisOffsets(x, a, d) m.action.d <- null Line 5 of this procedure is testing for "a.segment != undefined". But it seems to me that this must always be true, since the segments for all atoms get defined in SetSegment(). It seems to me that either the test isn't right, or there must be a missing line somewhere that says "a.segment <- undefined". Is there a typo somewhere here? Thanks for any help you can give me on this. Cheers! Forrest H Bennett III Visiting Scientist bennett@pal.xerox.com FX Palo Alto Laboratory, Inc. ----------- From: Marsette Arthur Vona To: Subject: Re: Your thesis Date: Thu, 1 Jun 2000 08:27:11 -0400 (EDT) Pleased to hear from you Mr. Bennett. Yes, you are correct, there is a mistake in the writeup. Change the line IF there exists an Atom a in x where a.segment != undefined to IF there exists an Atom a in x where displacement[a.segment].d != undefined That makes much more sense, and it agrees with my C implementation. The idea is that we are going to look for some Atom in this axis that already knows where it's going. Then starting from that locked-down Atom we can walk in both directions along the axis, noting Atoms that will be expanding or contracting in the current dimension, assigning displacements to every not-yet-proecessed segment we pass by, and verifying the displacements of every already-processed segment we pass by. ----------- From: Forrest Bennett To: "'vona@ai.mit.edu'" Subject: Something missing in CalculateAxisOffsets? Date: Thu, 1 Jun 2000 19:05:10 -0700 Hi Marty, I'm down to the last procedure, and it seems like something is wrong with CalculateAxisOffsets(). This loop: Integer shift <- HalfSize(a, d) FOR EACH Atom m along the i direction in x, in order and starting from a { body } Seems to be accumulating more and more shift for _every atom_ in the axis x. But I thought we should only be accumulating additional shift for each _segment_ in the axis, not each _atom_ in the axis? I have been looking at changing it along these lines: Integer shift <- 0 FOR EACH Atom m along the i direction in x, in order and starting _AFTER_ a, where displacement[m.segment].d == undefined { body } But that's still not quite right. Am I interpreting the loop incorrectly, or is something missing? Somehow it seems like the loop should go from segment to segment, not atom to atom. And that we don't want to be picking up any shift from atom a like we do in: Integer shift <- HalfSize(a, d) If you can see an error in the code as is, I'd love to know. Otherwise, I'll just try harder to understand it. Forrest Forrest H Bennett III Visiting Scientist bennett@pal.xerox.com FX Palo Alto Laboratory, Inc. ----------- From: Marsette Arthur Vona To: Forrest Bennett Subject: Re: Something missing in CalculateAxisOffsets? Date: Fri, 2 Jun 2000 12:30:45 -0400 (EDT) > I'm down to the last procedure, and it seems like something is wrong with > CalculateAxisOffsets(). Yes, you seem to be right. I think all we have to do is change the values returned by HalfSize(). Instead of returning 2, return +1. Instead of returning 1, return -1. And instead of returning (1/2)*(Size(a,d)) return 0. The idea is that HalfSize(a, d) will now return half of the "difference" in size of Atom a *if* a is an unprocessed mover (otherwise it will return 0, thus effectively skipping all Atoms except movers). By "difference" I mean for example if a is currently contracted and it is specified to expand, then the difference is +2, or conversely if a is currently expanded and is specified to contract then the difference is -2. I am pretty sure this is how I intended the pseudocode to be. Unfortunately at this point in the algorithm the pseudocode does not match 1:1 with the implementation (I forgot exactly why...). Note that when I say Direction i then i is +1 for the positive direction and -1 for the negative direction. Also, I noticed that the last line in CalculateDisplacements() seems to be redundanti, because the last line in CalculateAxisOffsets() should mark every mover in axis x as processed. Let me know if you think this fixes things. Marty ----------- From: Forrest Bennett To: "'vona@ai.mit.edu'" Subject: Thank you again Date: Fri, 2 Jun 2000 09:32:48 -0700 Marty, Thanks a million for the page 43 errata. I ran those changes by hand, and now it works perfectly for me. I hope that I can return the favor sometime. Have a great weekend! Forrest ----------- From: Forrest Bennett To: "'vona@ai.mit.edu'" Subject: Possible trouble in CalculateAxisOffsets Date: Tue, 6 Jun 2000 15:34:19 -0700 Hi Marty, It seems that there is a problem in CalculateAxisOffsets. Consider the following example with only two atoms. A fully expanded ground atom centered at 0,0,0 and a second fully expanded atom on top of it centered at 0,4,0. Now have the second atom undergo a contraction in the X dimension. When we execute CalculateDisplacements for dimension X, the WHILE loop selects our second atom as having a non-null action, and the IF statement selects that same atom as have a defined displacement in the X dimension. So we make the call to CalculateAxisOffsets(axis, atom, dimension) with the axis containing only our second atom, the atom being our second atom, and the dimension being X. Then we come into CalculateAxisOffsets, shown here with line numbers for reference: 1 CalculateAxisOffsets(Axis x, Atom a, Dimension d) 2 FOR EACH Direction i 3 Integer shift <- HalfSize(a, d) 4 FOR EACH Atom m along the i direction in x, in order and starting from a 5 shift <- shift + HalfSize(m, d) 6 abs_shift <- displacement[a.segment].d + i*shift 7 IF displacement[m.segment].d != undefined THEN 8 IF displacement[m.segment].d != abs_shift THEN 9 ABORT 10 ELSE 11 displacement[m.segment].d <- abs_shift 12 shift <- shift + HalfSize(m, d) 13 m.action.d <- null Line 3, sets shift = -1. Line 5, sets shift = -2. Line 6, sets abs_shift = -2. Line 7, the conditional is TRUE because (displacemtn[m.segment].d = 0). Line 8, the conditional is FALSE because (0 != -2). Line 9, ABORT error. I think the correction is to start the FOR loop on line 4 at the atom after a in direction i. Also, line 13 is a problem as is, because the action for atom a should not be null-ed out until after you process the other direction in the FOR loop on line 2. Changing the loop on line 4 to start after atom a solves both problems, but you would also need to add the line "m.action.d <- null" back into the last line of CalculateDisplacements. Let me know if you agree. And thanks again for your help. Forrest ----------- From: Marsette Arthur Vona To: Forrest Bennett Subject: Re: Possible trouble in CalculateAxisOffsets Date: Tue, 6 Jun 2000 19:03:14 -0400 (EDT) > Changing the loop on line 4 to start after atom a solves both > problems, but you would also need to add the line "m.action.d <- null" back > into the last line of CalculateDisplacements. Yes I think you're correct. In my mind I had always read line 4 to mean "starting *after* a" instead of what it really says, which is "startinig *from* a", and which implies that a is actually included. And yes, that must be why I had the last line of CalculateDisplacements() as it was. Thanks for pointing this out, Marty ----------- From: Forrest Bennett To: "'Marsette Arthur Vona'" Subject: Simulator update Date: Thu, 8 Jun 2000 11:31:40 -0700 Hi Marty, My simulator is mostly working, thanks for your help. I thought I might run the following thoughts by you: 1. I had to remove "in axis x" from the WHILE loop in CalculateDisplacements. Sometimes there is no atom in the same axis with the displacement defined in the needed dimension. In that case, it is necessary to get the displacement value for the segment from outside axis x. 2. It is possible for the final configuration to end up in a state where two bonded atoms that had an active face between them to get moved so that their faces no longer align. (I can send a simple example if you disagree.) So I just added a check at the end of the expansion update for this condition. 3. Both of the above issues would not arise if segments were defined slightly differently. Instead of assigning each atom to a segment and computing displacements for each dimension of that segment, I think it might work to assign each atom to an X segment, Y segment, and Z segment separately. Then you would compute the displacement values in the same way. This change would insure that item #2 above never happened, and also that in item #1 above you would always have an atom in the axis with the segment displacement you need. 4. I'm sure you're already aware that it's possible to generate intermediate states with collisions which arrive at a valid final state. For example: Before state: AAAAAAAAAA X X X C B X X XXXXXXX After state: AAAA X X X B C X X XXXXXXX The modules labeled A in the before diagram contract and cause the module B to pass through module C and then arrive at a final valid state. Since the expansion update process does not actually generate the intermediate states, detecting these kinds of situations can be somewhat tricky. Forrest ----------- From: Marsette Arthur Vona To: Forrest Bennett Subject: Re: Simulator update Date: Thu, 8 Jun 2000 15:26:12 -0400 (EDT) > 1. I had to remove "in axis x" from the WHILE loop in > CalculateDisplacements. Sometimes there is no atom in the same axis with the > displacement defined in the needed dimension. In that case, it is necessary > to get the displacement value for the segment from outside axis x. My intention there was to just have the whole while loop move on to some other unprocessed Atom m in C, continuing until an m is found for which there is some Atom a in the d axis of m that belongs to a segment whose displacement has already been calculated. Maybe not the fastest scheme, no. > 2. It is possible for the final configuration to end up in a state where two > bonded atoms that had an active face between them to get moved so that their > faces no longer align. (I can send a simple example if you disagree.) So I > just added a check at the end of the expansion update for this condition. Let's see, are you talking about a situation like 023 0 1 000 where each numeral i represents an Atom in segment i, every Atom is initially fully expanded, every possible inter-Atomic interface is bonded, segment 0 has had its displacements set to 0, and the Atoms labeled 2 and 1 are specified to contract in the horizontal and vertical dimensions, respectively? Then the Atom labeled 3 will crash, and I think you're right, this would not be detected with the current CheckFeasibility() routine. > 3. Both of the above issues would not arise if segments were defined > slightly differently. Instead of assigning each atom to a segment and > computing displacements for each dimension of that segment, I think it might > work to assign each atom to an X segment, Y segment, and Z segment > separately. Then you would compute the displacement values in the same way. > This change would insure that item #2 above never happened, and also that in > item #1 above you would always have an atom in the axis with the segment > displacement you need. Good idea. I think that solves #2, but I don't see yet how that solves #1. For example consider the initial Crystal 234 012 4 where the same initial conditions apply as above and Atoms 1 and 3 are specified to contract in the horizontal dimension. If the while loop in CalculateDisplacements picks Atom 3 as its first m then it won't be able to find a suitable Atom a (neither 2 nor 4 belong to segments that have assigned displacements yet), and this will be the case even if you do segment assignment on a per-dimension basis (which will come out the same as the current segment assignment in this specific instance because all active interfaces are parallel, right). The while loop needs to move on to Atom 1 as m, so that it can use Atom 0 as a. I do think that #2 is a much more important issue though. > 4. I'm sure you're already aware that it's possible to generate intermediate > states with collisions which arrive at a valid final state. For example: > > Before state: > AAAAAAAAAA > X X > X C B > X X > XXXXXXX > > After state: > AAAA > X X > X B C > X X > XXXXXXX > > The modules labeled A in the before diagram contract and cause the module B > to pass through module C and then arrive at a final valid state. Since the > expansion update process does not actually generate the intermediate states, > detecting these kinds of situations can be somewhat tricky. Yes, such collisions are not detected. If you are interested in preventing them you could calculate the swept volume for each segment (which should all be linear extrusions I believe) & then do all pairwise intersection tests between the swept volumes. What do you think of that? Thanks, Marty ----------- From: Forrest Bennett To: "'vona@ai.mit.edu'" Subject: RE: Simulator update Date: Thu, 8 Jun 2000 19:25:30 -0700 Marty wrote: > > 1. I had to remove "in axis x" from the WHILE loop in > > CalculateDisplacements. Sometimes there is no atom in the > same axis with the > > displacement defined in the needed dimension. In that case, > it is necessary > > to get the displacement value for the segment from outside axis x. > My intention there was to just have the whole while loop move > on to some other unprocessed Atom m in C, continuing until an > m is found for which there is some Atom a in the d axis of m > that belongs to a segment whose displacement has already been > calculated. Maybe not the fastest scheme, no. I'm not really worried about the speed yet, I'm concerned that a certain case is just not handled at all. Consider the configuration: 012 Where all three atoms are fulled expanded and bonded and 0 is the ground atom. Now expand atom 1 horizontally and expand atom 2 vertically. The problem is that atom 2 will never have any atom in it's Y axis with a defined displacement, and it will never have any atom in it's segment with a defined Y displacement. So CalculateDisplacemetns() just loops forever. I have created a new function to handle this class of cases. > > > 2. It is possible for the final configuration to end up in > a state where two > > bonded atoms that had an active face between them to get > moved so that their > > faces no longer align. (I can send a simple example if you > disagree.) So I > > just added a check at the end of the expansion update for > this condition. > Let's see, are you talking about a situation like > > 023 > 0 1 > 000 > > where each numeral i represents an Atom in segment i, every > Atom is initially fully expanded, every possible inter-Atomic > interface is bonded, segment 0 has had its displacements set > to 0, and the Atoms labeled 2 and 1 are specified to contract > in the horizontal and vertical dimensions, respectively? > Then the Atom labeled 3 will crash, and I think you're right, > this would not be detected with the current > CheckFeasibility() routine. Agreed. And the code to detect this case after the fact was easy. > > > 3. Both of the above issues would not arise if segments were defined > > slightly differently. Instead of assigning each atom to a > segment and > > computing displacements for each dimension of that segment, > I think it might > > work to assign each atom to an X segment, Y segment, and Z segment > > separately. Then you would compute the displacement values > in the same way. > > This change would insure that item #2 above never happened, > and also that in > > item #1 above you would always have an atom in the axis > with the segment > > displacement you need. > Good idea. I think that solves #2, but I don't see yet how > that solves #1. For example consider the initial Crystal > > 234 > 012 4 > > where the same initial conditions apply as above and Atoms 1 > and 3 are specified to contract in the horizontal dimension. > If the while loop in CalculateDisplacements picks Atom 3 as > its first m then it won't be able to find a suitable Atom a > (neither 2 nor 4 belong to segments that have assigned > displacements yet), and this will be the case even if you do > segment assignment on a per-dimension basis (which will come > out the same as the current segment assignment in this > specific instance because all active interfaces are parallel, > right). The while loop needs to move on to Atom 1 as m, so > that it can use Atom 0 as a. I agree again. My proposed change to the segment definition does not solve this. > > I do think that #2 is a much more important issue though. > > > 4. I'm sure you're already aware that it's possible to > generate intermediate > > states with collisions which arrive at a valid final state. > For example: > > > > Before state: > > AAAAAAAAAA > > X X > > X C B > > X X > > XXXXXXX > > > > After state: > > AAAA > > X X > > X B C > > X X > > XXXXXXX > > > > The modules labeled A in the before diagram contract and > cause the module B > > to pass through module C and then arrive at a final valid > state. Since the > > expansion update process does not actually generate the > intermediate states, > > detecting these kinds of situations can be somewhat tricky. > Yes, such collisions are not detected. If you are interested > in preventing them you could calculate the swept volume for > each segment (which should all be linear extrusions I > believe) & then do all pairwise intersection tests between > the swept volumes. What do you think of that? Sounds good. I'll code up something like that. Forrest ----------- From: Forrest Bennett To: "'vona@ai.mit.edu'" Subject: It works! Date: Sun, 11 Jun 2000 21:42:01 -0700 I have tested the simulator now on sequences of over 10 million random actions, as well as unit testing on selected cases. Changing how the segments are defined took care of the remaining issues. Now there is just the issue of the collisions in intermediate states. I have the visualizer for 2D running as well. Thanks a million for all your help on this!!! Forrest