Back to CS 4260/5260 main page.

Programming assignments are listed from most recently assigned down to the first assigned.

Programming Project 4

Program 4 requires that you interface your Program 3 solution with an LLM API, which will be used to summarize a road trip in narrative (and hopefully enticing) form.

At a minimum, write a function Give_Narrative (RoadTrip) that creates a prompt to the chosen LLM to give a narrative description of the road trip,  including attractions at the various locations and edges that the LLM recommends. You will have to decide how much a prompt created by Give_Narrative should include attractions that are part of the database of attractions  from which the roadtrip was created, or whether to leave the LLM to rely on its own place-based knowledge, or some combination of both.

Deliverable: Submit the following.

• Fully documented source code listing, or pointer to one that is accessible to Doug and Kyle, with a ReadMe file.
• A report of approximately 5 pages that includes
  • An overview of what you’ve done, which which focuses on your Give_Narrative function. Included in this introduction should be anything. you did above and beyond the minimally-required Give_Narrative function (1. Introduction)
  • The hand-crafted regression tree that you selected for tests reported herein. This can be the same as used in Program 3 or it can be a different tree. Include this in section 2. Experimental Design.
  • A couple of paragraphs on on tests with inclusion and exclusion constraints, as well as a description of your formula for computing overall utility. These can be the same as in Program 3 or different. This is also part of section 2. Experimental Design.
  • The experimental results with a subsection for each of three road trip inclusion/exclusion constraints, one road trip found for each (using same format as Program 1), road trip utilities, and average runtime over the three road trips found (as in Program 1) for each set of constraints the LLM prompt created by the Give_Narrative function for that road trip, and the LLM generated narrative for the road trip. For each subsection give your reactions to the narrative produced (3. Experimental Results)
  • Include 4. General Discussion to include the following.
    • If you used AI to implement, evaluate, document your software  in any of the program assignments, then 1 or more paragraphs of the experience and any insights on  strengths and weaknesses, to include insights from “ChatGPT Prompt Patterns for Improving Code Quality, Refactoring, Requirements Elicitation, and Software Design” by White, et al. (required reading).
    • You must include a discussion on how your function Give_Narrative used patterns/concepts from “A Prompt Pattern Catalog to Enhance Prompt Engineering with ChatGPT” by White, et al. to craft the prompts (required reading).
    • Include a discussion on how the use of both search-based deliberative AI and reflexive AI in the form of ANNs/LLMs in Program 4, relates to using LLMs exclusively, for both the road trip planning and the narrative description of the road trip. At a minimum include reference to  “Can Large Language Models Reason and Plan?” by Subbarao Kambhampati (required reading)
    • Discuss the what might be done in the future to extend the system further (such as other ways that the LLM can be used in the context of a road trip recommender system).
  • 5. Concluding remarks

  If this comes out to fewer than 5 pages, or more than 5 pages, 1.5 spacing, 1 inch margins, 12 pt  font, then that’s fine.

See the course schedule for the due date of the deliverable.

Programming Project 3

Program 3 requires that you expand upon the road trip recommender system in two ways.

• Regression tree guidance. Modify the system so that it consults a regression tree to identify the preferences of a user. In principle this regression tree (or forest of such trees) would be learned from a user’s (training) data, but for purposes of illustrating this functionality you are to hand craft a regression tree. The intent is that in evaluating the overall utility of a road trip, the regression tree is consulted for each location and edge on the candidate road trip, where individual internal nodes of the regression tree are individual themes that are represented (or not) on edges and locations, a path of internal nodes represents a set of theme values (present or absent) found (or not) at a location or edge, and leaves are utility values (in the interval [0 to 1]) that are associated with the corresponding path’s set of theme values. Implicit in a regression tree are implementations of concepts such as substitutability, additive utility, complementary and substitute factors (12.1)
  • You must define a function to compute a road trip’s predicted overall utility from the assessments of each of its location/edge predicted utilities.
• User control. Modify the system to include more user control into search. Notably, allow the user to provide a set of required locations and a set of forbidden locations that must be part of the road trip, or not part of the road trip. Returned road trips should still tend to be highest utility and to not violate time constraints, under the constraints provided.

Deliverable: Submit the following.

• Fully documented source code listing, or pointer to one that is accessible to Doug and Kyle, with a ReadMe file.
• A report of approximately 5 pages that includes
  • An opening paragraph overview of what you’ve done (1. Introduction)
  • Two hand-crafted regression trees that you considered, and the one you selected for tests. reported herein.
  • A couple of paragraphs on experimental design on tests with inclusion and exclusion constraints, as well as a description of your formula for computing overall utility (2. Experimental Design))
  • The experimental results showing “a table” (or subsections) of three road trip inclusion/exclusion constraints, three road trips found (using same format as Program 1), road trip utilities, and average runtime over the three road trips found (as in Program 1) for each set of constraints (3. Experimental Results)
  • If you used AI to implement, evaluate, document the systems then 1 or more paragraphs of the experience and any insights on  strengths and weaknesses (4. General Discussion)
  • 5. Concluding remarks

  If this comes out to fewer than 5 pages, or more than 5 pages, 1.5 spacing, 1 inch margins, 12 pt  font, then that’s fine.

See the course schedule for the due date of the deliverable.

Looking ahead: In Program 4 you will interface Program 3 with an LLM API, which will be used to summarize a road trip in narrative (and hopefully enticing) form.

—————————— End of Program 3 specification ——————————–

Programming Project 2

Program 2 has you construct and test methods of machine learning on data about a user’s preferences for locations and for edges. Program 2 requires that we conceptually expand our treatment of utilities beyond a single real number per location and per edge. Rather, single real values for utilities are computed from themes (aka factors aka features), each of which is assumed to have a micro-utility in the mind of a user. For example, a user may really like civil rights history – one theme (or factor) — and the same user may not like amusement parks as much. So the user will prefer locations and edges that feature civil rights histories to locations and edges with only amusement park attractions. Of course, each location and edge can be associated with attractions covering many themes, and a location’s factored utility for a user is some function of the micro utilities of the user for the themes that characterize the location/edge attractions. The function to compute an overall factor utility (or location and edge preference) over theme utilities will be learned from data on locations, edges, attractions, and themes.

Background/Context: Here is some context that will help in your understanding of terms. Suppose you have a tool that is based on your task for Program 1 – to find and present round trip road trip suggestions to a user, perhaps augmented with a visual overview of the trip, as well as a summary of potential attractions at locations and on edges. Don’t worry about the details of the recommender interface for now, except suppose that it has a slider so that when a road trip is suggested the user can use the slider to give an overall real-valued utility for the suggested road trip from 0.0 to 1.0. This is only a pre-trip projection of course, but it can always be adjusted later with a post-trip correction. The intent behind the interface’s design is to gather information about a user’s preferences while demanding relatively little of the user.

So what we have from this interaction with the round trip road trip recommender interface is a set of road trips, each associated with a single utility score between 0.0 and 1.0. We will assume that such data is all preprocessed into a dataset of themes and utility. You will be given a data set of the following form:

Data Set =

{ (U1 T11, T12, T13, …, T1m),

(U2 T21, T22, T23, …, T2m),

(U3 T31, T32, T33, …, T3m),

. . .

(Un Tn1, Tn2, Tn3, …, Tnm)}

Uk is the utility of the kth road trip , and Tkj is a count of the number of times that the theme Tj appears at a location and/or edge in the kth road trip. You need not worry about how the preprocessing occurs. because you are given the data as a csv file as formatted above, but you should read Section 12.1 of Poole and Mackworth (reading assignment for Week 6), and you should understand how the artificial data set on which you will test your learning algorithms was actually generated.

The data set itself is given here. It is formatted appropriate for supervised learning.

(a) In the case of learning decision trees, the utilities (the target or dependent variable) is divided into five discrete ranges, thus making performance a classification task. The 5 ranges are: ‘great’ is equivalent to [0.8, 1.0], ‘good’ is equivalent to [0.6, 0.8), ‘ok’ is equivalent to [0.4, 0.6), ‘low’ is equivalent to [0.2, 0.4), and ‘very low’ is equivalent to [0.0, 0.2). You will preprocess the data so that each Uk is replaced by one of the 5 labels from ‘great’ to ‘very low’.

(b) In the case of learning with back-propagation, the utilities are kept as real valued, thus making performance a regression task. The dataset that you are given is suitable for training a back-propagation network with m input units and 1 output unit.

The independent variables are the same for (a) and (b).

Deliverables: You will implement

• decision tree learning using the top-down induction method, and
• backpropagation using artificial neural networks with at least one hidden layer, in addition to an input and output layer. Again, the input layer should have one input node for each input feature in your back propagation data design, and one output node for the real valued utility.

This implementation must supply fully documented source code. You are allowed to use AI tools to help implement and document the software, but you cannot use off the shelf library implementations of these systems. I want you to actively think through the code.

Evaluation of the systems will use 5-fold cross validation, measure prediction accuracy in the case of decision tree induction experiments and mean-square error in the case of back propagation. For decision tree experiments you will vary the maximum depth of decisions, looking at max depth of 2 (the root is at depth 0) and max depth 5. Revise the top-down induction of decision trees from lecture (and the text) so that the domain of variables and classes can vary rather than all being binary valued. For back propagation experiments you will vary the number of hidden units, looking at 4 hidden units and 8 hidden units, so unlike the definition here you should implement a version that allows you to vary the number of hidden units, and optionally you can parameterize the number of hidden layers too.

You will submit a report of approximately 5 pages that includes tables reporting the mean accuracies and variance (for DTs) over the 5 folds for each max depth, and mean MREs and variance (for back propagation) over the 5 folds for each hidden layer size.

The bare minimum that we would like to see in your report is

• An opening paragraph overview of what you’ve done (1. Introduction)
• A couple of paragraphs on experimental design (2. Experimental Design))
• The experimental results in table form as described in lecture, plus a brief narrative description, notably a summary of the differences between the two DT conditions (accuracy/variance differences between max depths of 2 and 5), and between the two backprop conditions of number of hidden units. (3. Experimental Results)
• Your hypotheses about why the  two conditions for each learning system vary between experimental conditions, informed by your knowledge of the respective learning methods. (4. Discussion of Results, part a)
• Your comments relating the DT results and the backprop results, remembering that the DT results are in terms of accuracy and backprop results are in terms of error (i.e., accuracy and errors are inverses), and that the DT results are categorization (finite, discrete, ordered classes) and backprop prediction is along a continuous dimension. Are the two sets of results comparable in any way? Analyses will potentially vary considerably across submissions. (4. Discussion of Results, part b)
• If you used AI to implement, evaluate, document the systems then 1 or more paragraphs of the experience and any insights on  strengths and weaknesses (5. General Discussion)
• 5. Concluding remarks

If this comes out to fewer than 5 pages, or more than 5 pages, 1.5 spacing, 1 inch margins, 12 pt  font, then that’s fine.

Additionally, some submissions might go beyond the specs, for example tests with different DT pruning strategies and different backprop activation functions. Such efforts are eligible for bonus points that will essentially be extra credit.

—————————— End of Program 3 specification ——————————–

Programming Project 1

Specification

Program  1  will perform an anytime, utility-driven search for round-trip road-trips in a network of locations connected by road segments. The anytime search returns alternative, different roundtrips, one at a time, until the user says to stop. Its desirable that a roundtrip road-trip should have high utility as measured by a utility function, but that the road trip must also take no more than a specified maximum amount of time.

To perform an anytime utility-driven, time-constrained search will require bases for computing utility and for estimating time.

1) You will create a local and team-specific copy of the first two sheets of locations and edges for Program 1 . Copy the first two sheets  into csv files, EdgeFile and LocFile, . Ignore the last two sheets for this assignment. See the section Background below for an explanation of edges and locations.

2) You will augment each location and edge with its own preference value. For purposes of testing on Program 1 do the following.

a) Write a function called location_preference_assignments (a, b) that assigns random values between a=0 and b=1 inclusive using a uniform distribution to each location independently.

b) Write a function edge_preference_assignments (a, b) that assigns random values between a=0 and b=0.1 inclusive using a uniform distribution to each edge independently. Note that edges have a smaller preference upper bound than locations for Program 1.

3) Write a function total_preference (roadtrip) that returns the sum of all location and all edge preferences in a road trip. The roadtrip argument can be any graph of valid locations and edges – it need not be round trip, and it need not be connected — this is because the function can be called on partially constructed road-trips at intermediate points in search, as well as being called to evaluate the utility of a fully-connected round-trip. You decide on the internal representation of the roadtrip argument.

4) Write a function called time_estimate (roadtrip, x) that computes the time required by a road trip in terms of its constituent edges and locations as follows.

a) The time at a location is a function of the preference value, v_loc, assigned to the location – the greater the preference for a location, the more time spent at the location. Write a function time_at_location (v_loc) of your choice, under the constraint that if v_loc1 >= v_loc2, then t_loc1 >= t_loc2.

b) The base time required to traverse an edge is time t = d/x, where x is a specified speed in mph (e.g., x = 60), and d is the weight (distance in miles) of the edge. Note that x is assumed the same for all edges in Program 1.

c) An additional amount of time on an edge is a function of the preference value, v_edge, assigned to it. In particular, the additional time spent on an edge is computed by add_time_on_edge (v_edge), which for Program 1 will simply be a call to time_at_location (v_edge).

d) time_estimate (roadtrip, x) returns the sum of times at all locations and on all edges of the road trip using x as the assumed travel speed on edges. The roadtrip argument can be any graph of valid locations and edges – it need not be round trip, and it need not be connected (again, because this function will be used to estimate times of partially constructed round-trips at intermediate points during search, as well as on final, fully-connected round trips).

5) Write a top-level function

RoundTripRoadTrip (startLoc, LocFile, EdgeFile, maxTime, x_mph, resultFile)

that does an anytime search for round-trip road trips.

• Total round-trip road trip preference and time should not include preference and implied time of startLoc (which is also the end location of a round trip). Consideration of the startLoc can happen either inside or outside the total_preference and time_estimate functions — your choice.
• Road trips that are returned cannot exceed maxTime (in hours) and the search should be designed such that round trips with higher total preference are more likely to be found earlier than later. That is, if time_estimate(RTRT_j, x_mph) <= maxTime and time_estimate(RTRT_k, x_mph) <= maxTime and total_preference (RTRT_j, x_mph) > total_preference (RTRT_k) then its desirable (though not required) that RTRT_j be returned before RTRT_k.
• Note that there is no requirement that a round-trip road trip visit any location at most once, but there should be a bias for avoiding multiple visits to the same location (other than the start/end location). The leeway in making this a vias instead of an absolute requirement is that to reach some locations (e.g., a location on a “cul-de-sac”) may require multiple visits to other locations, on the way  to and from. In any case your time estimates and total preference (utility) should not double count visits to the same location on the same road trip.

A Test Run

A test run results from a single call to RoundTripRoadTrip (startLoc, LocFile, EdgeFile, maxTime, x_mph, resultFile).

Such a call will result in a sequence of solution paths (round trips), with the user answering ‘yes’ so that at least three solution paths result in the run.

Each solution path will be written to the screen and the resultFile, using the same format for both cases. Each solution path is identified by a unique program-generated solutionLabel. The user will then be asked whether another solution should be returned. If ‘yes’, then the anytime search continues. These steps can occur indefinitely until the user answers ‘no’, or until there are no more candidate solutions, at which time the search terminates. Again, there should be at least solution paths found per run.

Each solution path is essentially a sequence of edges that connect the start location back to the start location, with intermediate locations interLoc_i.

solutionLabel   startLoc  maxTime x_mph
1. startLoc   interLoc₁ edgeLabel  edgePreference  edgeTime  interLoc₁Pref  interLoc₁Time
2. interLoc₁ interLoc₂ edgeLabel  edgePreference  edgeTime  interLoc₂Pref  interLoc₂Time
…
N-1. interLoc_N-1 startLoc edgeLabel  edgePreference  edgeTime
startLoc  TotalTripPreference  TotalTripDistance  TotalTripTime

Each solution path is followed by a new blank line.

Each line of a solution path, except the first and last, corresponds to an edge between two locations with those labels given first and second on the line, followed by the edgeLabel between them, the edge preference value, the edge time (base + additional), and the preference and time of the second of the locations on the line.

After the user answers ‘no’ in a test run, a summary of the entire run should be written to the screen and to the resultFile. The summary includes

• the average instrumented runtime of all continuations of the search (that is, search time per solution paths, and do not include the time that search is paused between solutions so that you can answer yes/no).
• The maximum TotalTripPreference found across all solution paths (of which  there should be at least three)
• The average TotalTripPreference found across all solution paths (of which  there should be at least three)
• The minimum TotalTripPreference found across all solution paths (of which  there should be at least three)

Again, this summary will be written to screen and to the resultFile immediately following the last solution returned for a given test run.

While the data files provides undirected edges in the road network, each line of a solution gives a directed edge, in which the direction is from first location to the second location in the line of output. So your program will have to revise (or reinterpret) the undirected edges in the data file to be directed edges as appropriate in each solution path. (You could also interpret this as the data files contains a bidirectional edge, but in your output, one direction is specified). This shouldn’t be difficult.

Part A) Deliverables

You are to do at least three test runs (of at least three solution paths each), where there will be a separate resultFile for each run.

You will be submitting one BIG file and at least three smaller ones

• a fully documented program listing, to the extent possible placed in one file (for purposes of grading). Before the beginning of the program listing include (in order):

(a) comments at the top of file with Team number, team members;

(b) comments on how to run your code;

(c) anything notable about runtime or search strategy? (e.g., even though this is overtly a utility driven search in which goal-driven methods are not directly applicable, was there any way that you were able to use path cost and heuristic distance?)

Then give the program listing, with

(d) header comments for major functions.

After the end of the program listing give:

(e) qualitative comments on test runs (e.g., did any of your test cases correspond to situations in which no solution was possible? did your solutions monotonically decrease in value? did all test runs lead to solutions that met the hard time constraints?

(f) quantitative summary of test runs, notably

(i) the average of instrumented runtime of all continuations of all test runs (not including the time that search is paused between solutions so that you can answer yes/no).

(ii) the average  maximum TotalTripPreference found across all solution paths of all test runs;

(iii) the average TotalTripPreference found across all solution paths of all test runs;

(iv) the average minimum TotalTripPreference found across all solution paths of all test runs.

• resultFiles for at least 3 test runs (i.e., 3 anytime searches of at least three continuances each).

Background

For this project the road network has the following format.

A location is represented by latitude and longitude coordinates, and a name or label.

location_label  latitude   longitude

An edge is represented by a label, the two locations that the edge connects,  label A and label B, and an actual (on the ground) distance in miles between A to B (i.e., a weighted, undirected edge).

edge_label   location_label_A    location_label_B     actual_distance

For example, the following might be given in a road network (two files, one for locations and one for edges):

Location Label       Latitude      Longitude

NashvilleTN         36.174465    -86.767960

MemphisTN         35.117500    -89.971107

JacksonTN           35.614517    -88.813947

                       Edge Label                             Location1         Location2      Distance

Nashville_tofrom_Memphis_on_I40    NashvilleTN   MemphisTN       212

Nashville_tofrom_Jackson_on_I40      NashvilleTN   JacksonTN         129

Jackson_tofrom_Memphis_on_I40      JacksonTN     MemphisTN       88

The actual_distances are edge costs in the graph of cities. They are actual driving (or walking) distances, and are not straight-line, as-the-crow-flies distances. Note that the Nashville to Memphis edge is crossed out, because we will limit ourselves to edges between 50 miles and 200 miles, inclusive.

Guidelines on AI: You may use generative AI to help specify, design, implement, document, and evaluate your programs. In fact I encourage it. You can post openly on Piazza about ideas and designs for each program, but do not post code (though you can post prompts) unless Kyle and I approve it (e.g., you might share code for measuring runtime which you believe would help others.

The default programming language for the programs is Python, though if you really want to use a different language then make a pitch to Kyle and I.

—————————— End of Program 1 specification ——————————–

Back to CS 4260/5260 main page.