in reply to Finding the simplest combination of descrete thicknesses that sums nearest to the target thickness.

Am I the only one who got some shivers? Well I visited a couple weeks ago one of the 2 or 3 accelerators in the world (in Inage, Chiba, Japan) that uses heavy particles (carbon atoms I believe) for deep radiation therapy.. apparently invented at Berkeley, that was shut down and now just Germany and Japan can do this, explained as "a way to cure ovarian cancer without surgery". Right up your alley, I guess you must know these people. I saw one guy building a new PET scanner with 4 times the resolution too..

Well I only saw those metal masks you put where the beam hits, where you shape the hole to fit the shape of the tumor, this is totally different from what you are doing I believe.

I imagine if you look down on a patient lying on his back, if the radiation is coming from above, you basically would want something like a topographical map (like a 3D contour map). See this map to get an idea of what I mean. Mountain peaks are where it gets a few layers thick. Surely this would be optimum? You would use a single thickness lead sheet and cut it to make each layer of the map. Then you also wouldn't have vertical seams that could maybe burn the patient? There would be no packing problem then either.

That said, the (brass?) masks I saw did indeed seem to have been created by a computerized cutter, as the holes were made of many fine vertical cuts, perhaps <1mm in thickness and maybe more resolution in the y axis.

So my questions are:

1. Is this really the best solution? I mean you have to type in all those numbers, wouldn't it be better if you could go directly from some scanned data to a lead solution?

2. The other question is, this is all seems to be 2D, i.e. looking from the side at a cross section. But we're really talking about 3D, that is, an arrangement of many slabs all over the patient, more slabs in some places than others.

3. I feel pretty uncomfortable about how these threads tend to die quickly but you might need more help. I honestly don't think it's appropriate to be asking such important questions on this kind of a board when misunderstanding of a problem could jepoardize someone's life (though the basic ideas of packing and dynamic programming are of course good things to know). For example in the beginning I thought it was a student with a homework problem!
Maybe it's a problem with perlmonks that things are so evanescent (I still don't know how to view the list of nodes that showed on the homepage 2 days before). In particular I was wondering about whether vertical seams are dangerous, since it made me worry about a completely unattenuated beam burning a line into the patient if for example the pattern has a completely vertical seam, then how it is manufactured, i.e. could it come apart there, etc. That is how I came up with the idea of cutting each layer of a contour map with a jigsaw so there would be no seams and it could closely match the results of a CT scan, allowing much higher resolution than if you just type in the numbers (possibly making mistakes) yourself.

  • Comment on Re: Finding the simplest combination of descrete thicknesses that sums nearest to the target thickness.

Replies are listed 'Best First'.
Re^2: Finding the simplest combination of descrete thicknesses that sums nearest to the target thickness.
by doowah2004 (Monk) on May 05, 2005 at 15:55 UTC
    Every once in a while heavy particle radiation makes it back in the news, but it has lost favor with many hospitals because of the size of the accelerators. Most accelerators that are currently being used emit photons and/or electrons. The heavy particle accelerators emit either protons or neutrons. An electron is ~ 1000 times lighter than protons or neutrons, so they are much easier to accelerate. neutrons due not have charge, so the way that neutron beams are created is by colliding protons into the (although we are dealing with subatomic particles and quantum physics rule this domain, general mechanics of equal mass collisions are still a good approximate). Getting back to the size issue, an electron (linear) accelerator can fit in a room easily, but a proton accelerator is the size of a small building.

    The metal masks that you speak of are called blocks and are usually made of cerrobend.


    Now to answer your questions:

    1. The setup and treatment of total body irradiation is more complicated than taking a CT and building the filters that are required. BUT on a theoretic basis, yes you are correct, a continuous distribution would be best. BUT we do not live in a theoretical world. We have to look at complicity and cost v.s. gains. For TBIs, we are not treating cancer, we are trying to suppress the immune system to prepare the body for a transplant. It is not crittical to get absolute even dose over the entire body +/- 10% works fine.


    2. I think that #1 answers this, we are looking to correct gross changes. Also the beam enters the patient laterally (through the side), so imaging that you could see that it does become a 2d problem.


    3. Yes, these thread can die quickly, but then again there are threads that seem to never end. It all depends on the intrest level, and the area of the question. As far as burning the patient, we take every precaution to ensure that the patient is not mistreated. Currently this involve painstaking measures of creating the filters 4-6 hours per patient. We also take extreme care in the setup so that there are not any light leaks. That being said, we are changing the way that we make the blocks from a column type to a pyrimid type, and I am trying to write some software (as a tool) to quickly figure out the best way to do this. It is easy to do by hand, but can be time consumming. The software will only be a tool, and every thing that we do will be checked and double checked.



    Thank you everyone for your ideas and comments!
[reply]
      Thank you very much for your detailed comments and very interesting project.

      Yes, the site I visited was as you discuss, a medium sized building which cost $300 million to build, very expensive. Apparently using heavy particles (actually not just a proton but a whole carbon atom I believe) works well for deep targets but you know all this. It was very interesting though it was wierd to see even small children following the route which requires you to climb over and under the beam tube. Though the staff did not appreciate my asking (quietly to the side) if you would die from lethal x-ray dose etc. if you are in the donut shaped corridor holding the beam when it is turned on.. apparently it is accelerated to 80% of the speed of light.

      About the dose entering from the side it does seem (superficially to me sorry and I know nothing of course of diffraction in the body but..) there would be a shadow from bones or at least more radiation absorbed on the side of the body the radiation comes from? That is, I thought it is absorbed within a foot of the surface. Oh well sorry to bug you with silly questions, the packing and pyramid shaping ideas are quite interesting!

      I have not used it in large problems but just for fun there is Damian Conway's module series Quantum::Superpositions which provides the "any" and "all" words. It seems that some problems can be more easily stated in those terms, but really the best seems to me to try and make lots of blocks by hand and then translate some of the procedures you develop as you go along into bits of the program. Also possibly dynamic programming (blokhead mentioned this above it seems..) such as that used to find alignments of genetic sequences, where you solve many sub-problems first based on a set of scoring rules, then find a path through the solutions, to find the most efficient solution.

      The above approach is different from the way I was thinking about it, but the part I should stress is that depending on the scoring rules you create, a dynamic programming approach can create different outcomes as to what is the most efficient. Obviously, you might think, but it can be subtle. For example there is the Smith-Watermann method in genomics. You can end up with more sensitivity, or more preference for a certain type of solution, depending on whether you want to penalize certain kinds of mutations, gaps, or end features. In these cases it seems best to experiment with variations, and also consider statistical/practical issues (for example statistically where beam is coming from or what shapes are more dangerous, or what shapes are easier to build).

      If you are aligning two genetic sequences with dynamic programming, you end up drawing a matrix with one sequence (of letters A,T,G or C) for each axis. You start in the upper left corner and go right, then go to the next line when done. Basically you use the scoring rules to decide what score to write into a given cell, based on its coordinates and the contents of nearby (i.e. the previous) cell. When done filling in the whole matrix, you then go to the lower right hand corner and using another rule basically draw arrows towards the upper left corner, seeking the highest scoring valid cell. Basically this is supposed to give you the best sequence alignment and can be done by hand. So dynamic programming would suggest a similar kind of a procedure for your problem.

      Also it appears to me that we really want to solve this for the whole length of the body, in other words not just a single pyramid but a number of pyramids running from feet to head. So continuity will be important as a way to reduce cost (well unless you have only short pieces available) and to reduce seams. However it will become more computationally complex to solve for the whole body, and very hard to test a solution by eyeball to see if it makes sense. I wonder if I understand this correctly. If so, the seam between two pyramid units should be considered as a penalty and you have to have a piece that bridges the two.

      My own guess is that I would penalize cases in which vertical seams are created at all (since a single piece makes it easier to manufacture), and highly penalize a double seam (since a lot of radiation could leak through to sensitive tissue), if I am interpreting the pyramid to mean the beam is coming from the top of the pyramid, i.e. the base of the pyramid is actually against the patient's body, sideways, with the beam coming horizontally into the body from the top of the pyramid in through the base of the pyramid and then into the patient. In which case a vertical seam is bad, which is why you want to stagger or "build up" the pyramid like bricks.

      In this case the drawing tilly provided might not be selected, depending on the rules, because it has lots of vertical seams, both dangerous radiation wise as well as perhaps using too many strips (we are ignoring how many thick pieces you have available).

      Also you need to penalize or disallow solutions that are impossible to build (if they are?) such as a pyramid with a hole in it. To me it seems that you should be inputting not the widths and thicknesses of metal pieces, but the desired beam density at each coordinate, and a way to determine the beam density you get from a given solution, if that is what you are trying to determine.

      Anyway, the most important thing to do is to determine how to score potential solutions.

      Anyway, if you need something to get the juices flowing, here are some pages to look at: algorithm design and Design Patterns in Dynamic Programming. I just googled for "how to" and "dynamic programming" but also noticed that there are lots of kinds of "heuristic programming" methods. Also dynamic programming can take a long time for large data sets, maybe this is not a problem of yours.

      Finally, and this is not really my field, but there is a whole field of bin packing, set covering and partioning problems. One famous problem is the "knapsack problem". There are different algorithms that go by names like linear programming, simulated annealing, continuous relaxation and others. I'm not qualified to give you an overview of this sort of thing and my guess is that you don't have enough data to be worrying so much about the search algorithm, you should pay most attention to the definition of the problem.

      By the way I did find (google for radiation and "dynamic programming") a reference to computation of radiation doses PDF and as HTML from google. These people talk about something like what I hypothesized, using the CT scan to compute doses, but say it is too big a problem computationally and so use a heuristic called a Markov decision problem, or MDP. Anyway, google says that variants of dynamic programming are indeed used widely for radiation planning over time, though this is possibly a different problem from yours.

      Hope this thread helps you in working out this problem.

[reply]

In Section Seekers of Perl Wisdom