
\subsection{Question:}

\hspace*{1em}Design a simulation of Traffic Flow for a large busy city. 
This is to be a computer tool to assist in decision making for the city
planners on the following topics:
	\begin{itemize}
	\item 1 way streets
	\item on street parking
	\item street signals
	\item stop signs
	\item turn signals
	\item turning lanes
	\end{itemize}

You will need to discuss the following pieces of information:
	\begin{itemize}
	\item representation
	\item data gathering
	\item Algorithm (solution) approach
	\item Output
		\begin{itemize}
		\item graphics?
		\item other resources
		\end{itemize}
	\end{itemize}

Picture yourself as one of several bidders for this job.

\newpage
\subsection{Answer:}

\subsubsection{Overview:}
\hspace*{1em}I would probably begin the design around the use of a
processor for each intersection probably on some type of a mesh
architecture.  This would allow it to control all traffic coming into
that intersection, and then pass that data on stuff going out of the
intersection to it's appropriate neighbor.  There are several
advantages to this, such as when 1 intersection was coded they all
would be coded, and would just need the data for whatever particular
city you wished to simulate.


There are certain things I would need to know for each intersection:
	\begin{itemize}
	\item The number of Incoming neighbors (and who they are)
	\item The number of Outgoing neighbors (and who they are)
	\item Two way traffic?
	\item Number of lanes of traffic, each way.
	\item speed limit (for each incoming street)
		\begin{itemize}
		\item average gap kept between vehicles
		\end{itemize}
	
	\item distance (of each incoming street) from previous intersection 
		(how many vehicles can be packed in if a stoppage occurs)
	\item number of dedicated left turning lanes
	\item number of dedicated right turning lanes
	\item signals or stop signs? (for which incoming streets)
	\item Green light length
	\item Red light Length (gap size)
	\item right turn on red allowed?
		\begin{itemize}
		\item distribution of gap size for making turn
		\end{itemize}
	\item left turn on straight green allowed?
		\begin{itemize}
		\item distribution of gap size for making turn
		\end{itemize}
	\item Average for \% of vehicles that make a left turn. (by hour)
	\item Average for \% of vehicles that make a right turn. (by hour)
	\item Average for \% of vehicles that make no turn. (by hour)

	\item Bus (transit) information. -- 
		\begin{itemize}
		\item stop on this block?
		\item distance from intersection
		\item average for the  time spent at stop
		\item average  for \% of time this stop is used.
		\end{itemize}
	\item Parking garage on this street? 
		-- Maybe make this a separate intersection?
		YES.  Would make things a lot cleaner (and faster?) 
		\begin{itemize}
		\item size
		\item distribution for incoming and outgoing cars.
		\end{itemize}

	\item Non-Vehicular blockage 
		\begin{itemize}
		\item reasons
			\begin{itemize}
			\item reduction in number of usable lanes
			\item construction
			\end{itemize}	
		\item distance from intersection for start and stop.
		\item lane it is in
		\end{itemize}
	\end{itemize}

\subsubsection{Data Structures:}
	\begin{itemize}
	\item Some kind of object/data structure for each vehicle.
		\begin{itemize}
		\item number (if any) of special (fixed) rout required -- used
		for busses, \ldots
		\item speed
		\item Maximum deceleration (therefore gap size at any speed)
		\item location
		\item what direction it will go at this intersection. \\
		(assigned randomly) when object is passed in to this
		intersections control.

		\end{itemize}
	\item An array (linked list?) for the objects in this
	intersections control for each lane of each street coming into
	the intersection. 
		\begin{itemize}
		\item This would need allow quick insertion and
		deletion from each lane due to lane changes, exiting
		the intersections sphere of control, \ldots
		\item This would need to allow gap checking for
		adjacent lanes to a given vehicle. So he could change
		lanes if his lane is slowing down.
		\end{itemize}
	\end{itemize}

\subsubsection{Algorithm:}
	\begin{itemize}
	\item Update countdown for signal changes
	\item Tell neighbors the gap size at the back of each lane
		(this is where traffic would leave their control and
		enter your control).  If it is too small they would
		have to decelerate because of blockage.
	\item For each incoming street.
		\begin{itemize}
		\item move vehicles forward. front to back -- updating
		gaps between them.  Always keep gap between middle of
		the intersection and the first car (allows turn
		checking rapidly)
			\begin{itemize}
			\item Are you in the proper lane for exiting
			the intersection?
				\begin{itemize}
				\item if not try to change lane
				\item based on distance to intersection,
				slow down to force lane change.
				\end{itemize}
			\item is lane stopped?
				\begin{itemize}
				\item try to change lane -- unless you
				are within a fixed delta of
				intersection and you must be in a
				specific lane. Or other lanes are
				stopped at same distance or sooner.
				\end{itemize}
			\item am I having to decelerate (due to stoppage)
				\begin{itemize}
				\item is other lane not stopping, try
				to change lane
				\end{itemize}
			\item If front vehicle -
				\begin{itemize}
				\item is light green for me to go
				direction I need to? -- accelerate and go
				\item if not -- is it legal to go my
				direction (turn) and is the gap big
				enough? -- if so go.
				\end{itemize}
			\end{itemize}
		\item Accept incoming vehicles from neighbor.
			\begin{itemize}
			\item Assign direction out of intersection to
			each vehicle based upon distribution of this
			intersection - or special route. Possibly
			weight the distribution based upon current
			lane.
			\item Update totals for number of vehicles
			\end{itemize}
		\end{itemize}
	\end{itemize}

\subsubsection{Implementation Notes:}
	\hspace*{1em}This problem would probably map very nicely to a
	mesh architecture with quite a few processors, say a MASPAR
	SIMD machine which has a mesh $64 \times 128$ which could be
	laid out over the section of the city you wish to simulate.
	Given the fact that the average city has approximately 6 blocks
	per mile this would allow a mesh this size to overlay a $10
	\times 20$ mile area (most of any city).  The SIMD architecture
	would allow you to have a nice simple synchronization among all
	the processors so you did not have part of the grid way ahead
	of another part as could be possible in a simple message
	passing MIMD setup.

	\paragraph{Data Gathering:}
		This would be the hardest thing to do for the entire
	simulation, but would probably be the most important thing in
	making this as realistic as possible.  Besides the information
	at each intersection, you would need to know the rate at which
	cars entered the grid from the outside.  All of the rates
	mentioned in the data collecting could be in $\frac{cars}{min}$
	and could be updated every $\frac{1}{4}$ hour so the simulator
	could give realistic output as the day went along.  This data
	gathering for the rate entering the grid could be done with
	street counters that the highway department typically uses.
	The other data inside the grid might be the hardest to gather,
	and some of it may have to be approximated by using sub-grids
	throughout the city.  

		The one thing that could be a very nice thing for data
	counting would be newer light systems at intersections which
	are designed with a simple computer running them and builtin
	sensors for each lane coming into the intersection.  These can
	sometimes be programmed to dump the numbers (for each lane)
	that we would want.  If this were possible then we could get
	much more accurate data, over a longer period of time,  than
	would otherwise be possible

	\paragraph{Input:} 
	Input to the simulator would be data for each intersection
	describing the items listed above, as well as the rate of entry
	into the entire grid as mentioned previously.   Once this was
	loaded, and Buses were in place, the simulation could begin.

	Also you would need to know what time of day you wanted to start
	and how long you wanted the simulator to run.

	Initial placement of traffic is a consideration that would seem
	pretty arbitrary.  If you started the simulator at midnight, by
	4am, it should be up to a realistic flow of traffic, and ready
	to handle the entire days load.

	\paragraph{Output:}
	This could make or break the entire system.  Output that you
	would want would be things like the following:

		\begin{itemize}
		\item The average number of cars stopped at each
		stoplight.
		\item The standard deviation for the number of cars
		stopped at each stoplight.
		\item The maximum number of cars stopped at each
		stoplight.
		\item The minimum number of cars stopped at each
		stoplight.
		\item Any street that was filled so no cars could come
		through an intersection to go on that street.
		\end{itemize}

	This would allow you to mark every block that had above a
	certain threshold of cars slowed down (by intersections) per
	lane.


	
