Re: [math-fun] Model of road network development.
It's interesting that you mention arteries & capillaries. There has been some work on how arteries & capillaries develop in animals and humans. Sportspersons are particularly interested in the development of capillaries, as a higher % of capillaries in the muscles lead to greater performance and endurance. So-called "red" muscle fibers have better blood supplies than "white" muscle fibers. It is conjectured that the build-up of "waste" products like lactic acid encourages the development of more capillaries. Arteries can also increase in size with exercise -- at least in the young. It is conjectured that the eddies & vortices that form in smaller vessels somehow encourage the artery to grow -- perhaps from the vibration? The drug industry has investigated vascularization because one way to kill a cancer is to keep it from developing a good blood supply. So scholor.google.com may be able to help you find those who might have written similar simulation models. At 07:27 AM 3/24/2011, Allan Wechsler wrote:
I have been mulling over a possible simulation of the development of road systems, and for some reason I can't force myself to actually start writing code. I'm hoping that some math-funster will kick me out of my rut. My hope is that the model will generate realistic-looking road networks from scratch. I'm curious to see if it will capture some of the features we are used to in road networks: a preference for right-angled intersections, a fractal-ish vascularization of the area with major and minor arteries giving way to capillaries, and so on. And if it doesn't, I'm even more curious to know what kinds of networks it will generate instead.
We begin with a plane region, possible a square or a disk. At the beginning of the simulation, travel speed is a fixed constant, say 1 meter per second.
We select two points at random from the region, with a uniform distribution, and imagine that somebody needs to travel from one point to the other. The traveler selects the fastest possible route, and goes.
The act of traveling over a route increases the speed limit along that route by one centimeter per second. After that first journey, the travel speed is 1 meter per second everywhere, except along the line between those first two points; along that line, the speed is 1.01 meters per second.
We now select a new two points at random, find the shortest path by the modified metric, and perform the journey; again, the speed limit is increased by 0.01 meters per second along the chosen route. If the new endpoints lie near the original line, there will be an advantage in sidling toward that line, and scooting along it until the destination nears. (My algebra indicates that there is a critical angle at which it is most advantageous to join an existing route.)
After repeating this process thousands of times, what sort of road network will have developed?
Progressing to actual algorithm design: It's clear that the hard step is to find the fastest route from point A to point B in the presence of a big set of line segments, each with its own speed limit, with a base speed limit across undeveloped territory. If you were confined to the road network, it would be a graph traversal problem. But the fact that you can strike out overland makes things a little harder. I did some algebra that suggests that if the overland speed is 1 m/s, and you are approaching a road whose speed limit is u > 1, then whether it is smart to get on the road is based on the angle between your bearing and the road's. The critical angle is atan(u^2 - 1), unless I screwed up, which is entirely possible. If you are approaching the road at a steeper angle than that, you should just cross the road and keep going overland. If you are approaching at a shallower angle, then you should get on the road ... but you could do even better by steering toward the road and getting on sooner. This suggests that the optimal path will exit and leave roads at precisely the critical angle, which ought to simplify path searching somewhat. On Thu, Mar 24, 2011 at 1:29 PM, Henry Baker <hbaker1@pipeline.com> wrote:
It's interesting that you mention arteries & capillaries. There has been some work on how arteries & capillaries develop in animals and humans.
Sportspersons are particularly interested in the development of capillaries, as a higher % of capillaries in the muscles lead to greater performance and endurance. So-called "red" muscle fibers have better blood supplies than "white" muscle fibers. It is conjectured that the build-up of "waste" products like lactic acid encourages the development of more capillaries.
Arteries can also increase in size with exercise -- at least in the young. It is conjectured that the eddies & vortices that form in smaller vessels somehow encourage the artery to grow -- perhaps from the vibration?
The drug industry has investigated vascularization because one way to kill a cancer is to keep it from developing a good blood supply.
So scholor.google.com may be able to help you find those who might have written similar simulation models.
At 07:27 AM 3/24/2011, Allan Wechsler wrote:
I have been mulling over a possible simulation of the development of road systems, and for some reason I can't force myself to actually start writing code. I'm hoping that some math-funster will kick me out of my rut. My hope is that the model will generate realistic-looking road networks from scratch. I'm curious to see if it will capture some of the features we are used to in road networks: a preference for right-angled intersections, a fractal-ish vascularization of the area with major and minor arteries giving way to capillaries, and so on. And if it doesn't, I'm even more curious to know what kinds of networks it will generate instead.
We begin with a plane region, possible a square or a disk. At the beginning of the simulation, travel speed is a fixed constant, say 1 meter per second.
We select two points at random from the region, with a uniform distribution, and imagine that somebody needs to travel from one point to the other. The traveler selects the fastest possible route, and goes.
The act of traveling over a route increases the speed limit along that route by one centimeter per second. After that first journey, the travel speed is 1 meter per second everywhere, except along the line between those first two points; along that line, the speed is 1.01 meters per second.
We now select a new two points at random, find the shortest path by the modified metric, and perform the journey; again, the speed limit is increased by 0.01 meters per second along the chosen route. If the new endpoints lie near the original line, there will be an advantage in sidling toward that line, and scooting along it until the destination nears. (My algebra indicates that there is a critical angle at which it is most advantageous to join an existing route.)
After repeating this process thousands of times, what sort of road network will have developed?
Sounds like you're on your way.. but three more general thoughts. 1. *impact of terrain*. branching morphology appears to shift dramatically once terrain overrides the volume/velocity of whatever's in the vessel. If there are many cars or they need to go fast then the road will be cut into the terrain and you'll get smooth curves where there's a lot of traffic or high speeds (emphasizing the "or"). As speed approaches zero, or course, you'll get right angles as in sapling tree branches and rivers. As terrain dominates and digging costs override the benefits of a straight road the pattern shifts dramatically. These stretches are not merely narrow but as narrow as possible. They're also long (because if the distance were short it would be blasted out), jagged and lumpy (I think road pull-outs are an interesting analogy) like oak tree branches or lightning. So on windy mountain roads cars will travel single-file and very slowly (and in an inefficient pattern) even if total volume is high. 2. *fluid pressure*. there's something interesting going on with blood vessels that may be useful to know. Blood obviously travels in a loop through single, large diameter highways, in a sense, and then through a network of country roads and back to highways. Turns out an unexpectedly large pressure drop in the system occurs over the arterioles. Am not sure why. 3. *interaction*. Branches can connect existing things, or things can develop around branches, or both. The patterns are very different. - Gary On Thu, Mar 24, 2011 at 10:54 AM, Allan Wechsler <acwacw@gmail.com> wrote:
Progressing to actual algorithm design:
It's clear that the hard step is to find the fastest route from point A to point B in the presence of a big set of line segments, each with its own speed limit, with a base speed limit across undeveloped territory. If you were confined to the road network, it would be a graph traversal problem. But the fact that you can strike out overland makes things a little harder.
I did some algebra that suggests that if the overland speed is 1 m/s, and you are approaching a road whose speed limit is u > 1, then whether it is smart to get on the road is based on the angle between your bearing and the road's. The critical angle is atan(u^2 - 1), unless I screwed up, which is entirely possible. If you are approaching the road at a steeper angle than that, you should just cross the road and keep going overland. If you are approaching at a shallower angle, then you should get on the road ... but you could do even better by steering toward the road and getting on sooner.
This suggests that the optimal path will exit and leave roads at precisely the critical angle, which ought to simplify path searching somewhat.
On Thu, Mar 24, 2011 at 1:29 PM, Henry Baker <hbaker1@pipeline.com> wrote:
It's interesting that you mention arteries & capillaries. There has been some work on how arteries & capillaries develop in animals and humans.
Sportspersons are particularly interested in the development of capillaries, as a higher % of capillaries in the muscles lead to greater performance and endurance. So-called "red" muscle fibers have better blood supplies than "white" muscle fibers. It is conjectured that the build-up of "waste" products like lactic acid encourages the development of more capillaries.
Arteries can also increase in size with exercise -- at least in the young. It is conjectured that the eddies & vortices that form in smaller vessels somehow encourage the artery to grow -- perhaps from the vibration?
The drug industry has investigated vascularization because one way to kill a cancer is to keep it from developing a good blood supply.
So scholor.google.com may be able to help you find those who might have written similar simulation models.
At 07:27 AM 3/24/2011, Allan Wechsler wrote:
I have been mulling over a possible simulation of the development of road systems, and for some reason I can't force myself to actually start writing code. I'm hoping that some math-funster will kick me out of my rut. My hope is that the model will generate realistic-looking road networks from scratch. I'm curious to see if it will capture some of the features we are used to in road networks: a preference for right-angled intersections, a fractal-ish vascularization of the area with major and minor arteries giving way to capillaries, and so on. And if it doesn't, I'm even more curious to know what kinds of networks it will generate instead.
We begin with a plane region, possible a square or a disk. At the beginning of the simulation, travel speed is a fixed constant, say 1 meter per second.
We select two points at random from the region, with a uniform distribution, and imagine that somebody needs to travel from one point to the other. The traveler selects the fastest possible route, and goes.
The act of traveling over a route increases the speed limit along that route by one centimeter per second. After that first journey, the travel speed is 1 meter per second everywhere, except along the line between those first two points; along that line, the speed is 1.01 meters per second.
We now select a new two points at random, find the shortest path by the modified metric, and perform the journey; again, the speed limit is increased by 0.01 meters per second along the chosen route. If the new endpoints lie near the original line, there will be an advantage in sidling toward that line, and scooting along it until the destination nears. (My algebra indicates that there is a critical angle at which it is most advantageous to join an existing route.)
After repeating this process thousands of times, what sort of road network will have developed?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It strikes me that a form of controlled pseudo-DLA would provide a possible alternative algorithm. By pseudo-DLA I mean where "growth" is chosen simply by choosing a statistically appropriate growth direction on each step. On 24 Mar 2011, at 21:25, Gary Antonick wrote:
Sounds like you're on your way.. but three more general thoughts.
1. *impact of terrain*. branching morphology appears to shift dramatically once terrain overrides the volume/velocity of whatever's in the vessel. If there are many cars or they need to go fast then the road will be cut into the terrain and you'll get smooth curves where there's a lot of traffic or high speeds (emphasizing the "or"). As speed approaches zero, or course, you'll get right angles as in sapling tree branches and rivers.
As terrain dominates and digging costs override the benefits of a straight road the pattern shifts dramatically. These stretches are not merely narrow but as narrow as possible. They're also long (because if the distance were short it would be blasted out), jagged and lumpy (I think road pull-outs are an interesting analogy) like oak tree branches or lightning. So on windy mountain roads cars will travel single-file and very slowly (and in an inefficient pattern) even if total volume is high.
2. *fluid pressure*. there's something interesting going on with blood vessels that may be useful to know. Blood obviously travels in a loop through single, large diameter highways, in a sense, and then through a network of country roads and back to highways. Turns out an unexpectedly large pressure drop in the system occurs over the arterioles. Am not sure why.
3. *interaction*. Branches can connect existing things, or things can develop around branches, or both. The patterns are very different.
- Gary
On Thu, Mar 24, 2011 at 10:54 AM, Allan Wechsler <acwacw@gmail.com> wrote:
Progressing to actual algorithm design:
It's clear that the hard step is to find the fastest route from point A to point B in the presence of a big set of line segments, each with its own speed limit, with a base speed limit across undeveloped territory. If you were confined to the road network, it would be a graph traversal problem. But the fact that you can strike out overland makes things a little harder.
I did some algebra that suggests that if the overland speed is 1 m/s, and you are approaching a road whose speed limit is u > 1, then whether it is smart to get on the road is based on the angle between your bearing and the road's. The critical angle is atan(u^2 - 1), unless I screwed up, which is entirely possible. If you are approaching the road at a steeper angle than that, you should just cross the road and keep going overland. If you are approaching at a shallower angle, then you should get on the road ... but you could do even better by steering toward the road and getting on sooner.
This suggests that the optimal path will exit and leave roads at precisely the critical angle, which ought to simplify path searching somewhat.
On Thu, Mar 24, 2011 at 1:29 PM, Henry Baker <hbaker1@pipeline.com> wrote:
It's interesting that you mention arteries & capillaries. There has been some work on how arteries & capillaries develop in animals and humans.
Sportspersons are particularly interested in the development of capillaries, as a higher % of capillaries in the muscles lead to greater performance and endurance. So-called "red" muscle fibers have better blood supplies than "white" muscle fibers. It is conjectured that the build-up of "waste" products like lactic acid encourages the development of more capillaries.
Arteries can also increase in size with exercise -- at least in the young. It is conjectured that the eddies & vortices that form in smaller vessels somehow encourage the artery to grow -- perhaps from the vibration?
The drug industry has investigated vascularization because one way to kill a cancer is to keep it from developing a good blood supply.
So scholor.google.com may be able to help you find those who might have written similar simulation models.
At 07:27 AM 3/24/2011, Allan Wechsler wrote:
I have been mulling over a possible simulation of the development of road systems, and for some reason I can't force myself to actually start writing code. I'm hoping that some math-funster will kick me out of my rut. My hope is that the model will generate realistic-looking road networks from scratch. I'm curious to see if it will capture some of the features we are used to in road networks: a preference for right-angled intersections, a fractal-ish vascularization of the area with major and minor arteries giving way to capillaries, and so on. And if it doesn't, I'm even more curious to know what kinds of networks it will generate instead.
We begin with a plane region, possible a square or a disk. At the beginning of the simulation, travel speed is a fixed constant, say 1 meter per second.
We select two points at random from the region, with a uniform distribution, and imagine that somebody needs to travel from one point to the other. The traveler selects the fastest possible route, and goes.
The act of traveling over a route increases the speed limit along that route by one centimeter per second. After that first journey, the travel speed is 1 meter per second everywhere, except along the line between those first two points; along that line, the speed is 1.01 meters per second.
We now select a new two points at random, find the shortest path by the modified metric, and perform the journey; again, the speed limit is increased by 0.01 meters per second along the chosen route. If the new endpoints lie near the original line, there will be an advantage in sidling toward that line, and scooting along it until the destination nears. (My algebra indicates that there is a critical angle at which it is most advantageous to join an existing route.)
After repeating this process thousands of times, what sort of road network will have developed?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Ooops - sorry, I meant location and direction ! On 24 Mar 2011, at 23:37, David Makin wrote:
It strikes me that a form of controlled pseudo-DLA would provide a possible alternative algorithm. By pseudo-DLA I mean where "growth" is chosen simply by choosing a statistically appropriate growth direction on each step.
On 24 Mar 2011, at 21:25, Gary Antonick wrote:
Sounds like you're on your way.. but three more general thoughts.
1. *impact of terrain*. branching morphology appears to shift dramatically once terrain overrides the volume/velocity of whatever's in the vessel. If there are many cars or they need to go fast then the road will be cut into the terrain and you'll get smooth curves where there's a lot of traffic or high speeds (emphasizing the "or"). As speed approaches zero, or course, you'll get right angles as in sapling tree branches and rivers.
As terrain dominates and digging costs override the benefits of a straight road the pattern shifts dramatically. These stretches are not merely narrow but as narrow as possible. They're also long (because if the distance were short it would be blasted out), jagged and lumpy (I think road pull-outs are an interesting analogy) like oak tree branches or lightning. So on windy mountain roads cars will travel single-file and very slowly (and in an inefficient pattern) even if total volume is high.
2. *fluid pressure*. there's something interesting going on with blood vessels that may be useful to know. Blood obviously travels in a loop through single, large diameter highways, in a sense, and then through a network of country roads and back to highways. Turns out an unexpectedly large pressure drop in the system occurs over the arterioles. Am not sure why.
3. *interaction*. Branches can connect existing things, or things can develop around branches, or both. The patterns are very different.
- Gary
On Thu, Mar 24, 2011 at 10:54 AM, Allan Wechsler <acwacw@gmail.com> wrote:
Progressing to actual algorithm design:
It's clear that the hard step is to find the fastest route from point A to point B in the presence of a big set of line segments, each with its own speed limit, with a base speed limit across undeveloped territory. If you were confined to the road network, it would be a graph traversal problem. But the fact that you can strike out overland makes things a little harder.
I did some algebra that suggests that if the overland speed is 1 m/s, and you are approaching a road whose speed limit is u > 1, then whether it is smart to get on the road is based on the angle between your bearing and the road's. The critical angle is atan(u^2 - 1), unless I screwed up, which is entirely possible. If you are approaching the road at a steeper angle than that, you should just cross the road and keep going overland. If you are approaching at a shallower angle, then you should get on the road ... but you could do even better by steering toward the road and getting on sooner.
This suggests that the optimal path will exit and leave roads at precisely the critical angle, which ought to simplify path searching somewhat.
On Thu, Mar 24, 2011 at 1:29 PM, Henry Baker <hbaker1@pipeline.com> wrote:
It's interesting that you mention arteries & capillaries. There has been some work on how arteries & capillaries develop in animals and humans.
Sportspersons are particularly interested in the development of capillaries, as a higher % of capillaries in the muscles lead to greater performance and endurance. So-called "red" muscle fibers have better blood supplies than "white" muscle fibers. It is conjectured that the build-up of "waste" products like lactic acid encourages the development of more capillaries.
Arteries can also increase in size with exercise -- at least in the young. It is conjectured that the eddies & vortices that form in smaller vessels somehow encourage the artery to grow -- perhaps from the vibration?
The drug industry has investigated vascularization because one way to kill a cancer is to keep it from developing a good blood supply.
So scholor.google.com may be able to help you find those who might have written similar simulation models.
At 07:27 AM 3/24/2011, Allan Wechsler wrote:
I have been mulling over a possible simulation of the development of road systems, and for some reason I can't force myself to actually start writing code. I'm hoping that some math-funster will kick me out of my rut. My hope is that the model will generate realistic-looking road networks from scratch. I'm curious to see if it will capture some of the features we are used to in road networks: a preference for right-angled intersections, a fractal-ish vascularization of the area with major and minor arteries giving way to capillaries, and so on. And if it doesn't, I'm even more curious to know what kinds of networks it will generate instead.
We begin with a plane region, possible a square or a disk. At the beginning of the simulation, travel speed is a fixed constant, say 1 meter per second.
We select two points at random from the region, with a uniform distribution, and imagine that somebody needs to travel from one point to the other. The traveler selects the fastest possible route, and goes.
The act of traveling over a route increases the speed limit along that route by one centimeter per second. After that first journey, the travel speed is 1 meter per second everywhere, except along the line between those first two points; along that line, the speed is 1.01 meters per second.
We now select a new two points at random, find the shortest path by the modified metric, and perform the journey; again, the speed limit is increased by 0.01 meters per second along the chosen route. If the new endpoints lie near the original line, there will be an advantage in sidling toward that line, and scooting along it until the destination nears. (My algebra indicates that there is a critical angle at which it is most advantageous to join an existing route.)
After repeating this process thousands of times, what sort of road network will have developed?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Am I thinking about this wrong, or would this algorithm work (albeit at explosively escalating time and space): For iteration n, given start point a_n, end point b_n and existing roads Rn[], provisionally bump the speed limits on each Rn_i by one increment, create provisional roads R_ai from a to R_i and R_bi from b to R_i, where each R_ai is the shortest path from R_i to a, and the same for R_bi, create provisional road direct from a to b, Do the weighted graph traversal from a to b, Drop every provisional not part of the optimal traversal, Iterate. The O() is going to hurt, but otherwise it should work, yes? P.S. It would also be interesting to look at the railroad variant where large-angle crossings are not also intersections. -JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
participants (5)
-
Allan Wechsler -
David Makin -
Gary Antonick -
Henry Baker -
James Cloos