This repository contains the Project requirements for Artificial Intelligence class in Spring 2023 for the MS. of Computer Science program of Vanderbilt University.
by: Kevin Offemaria
The project requirements and relevant information are found in the directory: project_reqs.
For the required project submission documents, see dir: submission_files/part2.
test_cases_summary_part2.pdf
country-sched-architecture.jpg
CS5260_AI_koffemaria_part2.pptx
video_link_part2.txt
For part 1, see submission_files/part1.
- Correct implementation of Greedy Best First Search
using PriorityQueue.
- Pointing out that inverting EU scores is correct in my original part 1 implementation.
- Removed human intuition from resource weights.
- Fixed a bug from on the Transform template was doing unnecessary looping for all countries, but we only care about
Transforms of the
self.country
. As a result onevaluate_best_score()
, we only need to evaluate the EU score of our own self country. - Shuffling of child nodes before being evaluated for their EU scores.
- Add plots and summary schedules for more efficient analysis.
- Random encounters on applied on Transfer template to add more uncertainty on this action with a chance for both positive or negative effects.
- A chance to recycle applied during Transform templates to recover a small percentage of raw resources used.
- Increased complexity of State Quality
by adding a cap on
Electronics
to satisfy a country's population and slightly increasing a priority for populationHousing
. - A concept of entropy is implemented in the form of decaying resources using tiers of node count as the timestep.
- Implemented two new search strategies to the game, Heuristic Depth First Search and Breadth First Search.
Fallout is based on a post-apocalyptic world, and Electronics as a whole is considered to be it's the most valued produced resource. Intrinsically, Electronics can be defined as anything from radios, automobiles, firearms, etc.
In terms of the State Quality definition, a country values its happiness according to how much Electronics
it
currently owns. Therefore, its State Quality measure is the count of the amount of available Electronics.
Since Electronics is a produced resource, there is value in having the necessary raw materials to produce them though
it would still need resources and time to produce them. This continuity of production is counted towards the SQ
score but with a 50% penalty. All of these are reflected in the resource weights
There is a cap on Electronics against the country's population assumed at a 2:1 ratio of Electronics per person.
If a country has more Electronics against its own population, we penalize Electronics, MetallicElements, MetallicAlloys.
This is necessary to shift focus on other resources that may potentially increase population satisfaction
such as Housing
, which has an increased role in EU contribution. We assume the optimal ratio of persons to a house is
4:1, or 4 persons per single house. A bonus to this resource is applied to incentivize building houses to accommodate
a country's population. However, just like Electronics, once the limit goes above the ratio a penalty will be applied
to discourage building unnecessary houses for a satisfied population.
Finally, there is a small bonus applied to recycling ElectronicsWaste
due to the scarcity of resources in the
barren wasteland. We assume ~17% of e-waste is recycled contributing positively to EU score.
Logistic function constants:
x
is the input or independent variableL
is the maximum value of the functionk
is the logistic growth rate or steepness of the curvex_0
is the x-value of the sigmoid's midpoint
There are 3 search functions that can be used in the program: Greedy Best First Search, Heuristic Depth First Search, Breadth First Search. GBFS utilizes the PriorityQueue class from the Python library, queue, as the storage frontier. While the others use the built-in Python List object. The algorithm of all three functions is generally the same whereby they start with a root node inserted into the frontier and generate children nodes based on a root or parent node. It then attempts to generate Action Templates for TRANSFORMs and TRANSFERs. The resource values for the current node’s country are modified by the Action. The new child nodes are randomly shuffled and appended to the frontier. Next, the Expected Utility score on the current node is calculated and evaluated against the best scoring EU node. If so, replace the best EU node with the current node, and write all the Action Templates for all parent nodes of the current node. The program ends when the maximum depth, or frontier size has been exceeded, or the frontier is empty. See diagram below.
Test Case Results can be found here.
To install the project requirements:
# install python virtual environment
pyenv virtualenv 3.10.1 venv_name
pyenv activate venv_name
# install reqs file
pip install -r requirements.txt
The main program is the country_scheduler.py
. Many of the arguments have default values, so you may invoke the module
without passing any parameters.
Run this from the top level directory as follows:
# run with default args
python src/country_scheduler.py
# run with custom args
python src/country_scheduler.py
--country-self NewCaliforniaRepublic
--resource-file src/input_files/world_resources_1.csv
--state-file src/input_files/world_state_1.csv
--output-file src/output_files/bfs_results
--search_type gbfs # choices=["bfs", "hdfs", "gbfs"]
--num-schedules 20
--depth-bound 20
--frontier-size 10000
--loglevel INFO
- Test Results are found in the output_files
- The last few characters of the file name indicate the test case and iteration (eg.
bfs_res...test1a.txt
)
- The last few characters of the file name indicate the test case and iteration (eg.
- Initial states are found in input_files
- Main program in
src/
dir- entrypoint:
country_scheduler.py
- entrypoint:
submission_files/
contain the summary files as advised the project requirements.
├── project_reqs
│ ├── Part1
│ ├── Part2
├── src
│ ├── input_files
│ │ ├── world_resources_1.csv
│ │ ├── world_state_1.csv
│ ├── output_files
│ │ ├── result_graphs
│ │ ├── result_plots
│ ├── base_classes.py
│ ├── country_scheduler.py
│ ├── world_search.py
│ ├── util.py
├── submission_files
│ ├── part1
│ ├── part2
├── README.md
├── README_notes.md
├── requirements.txt
└── .gitignore
Class community citations:
- John Ford – Concept of Resource decay
- Karely Rodriguez – Proper implementation of HDFS, alpha-beta pruning
Online citations:
- E-waste recycling
- Fallout Random Encounters
- Greedy Best First Search
- Depth First Search
- Breadth First Search
- Metals deterioration
- Timber decay
Grade: 92
- I appreciate that you took the Part 1 comments and critiques and really did a good job of addressing each of the issues...each of the items of concern looks much better in this submission, so thank you for taking the time to address those. I hope that in making some of those changes, you were able to see an improvement in your agent's behavior and understand why they were needed.
- In your updated State Quality function, you say that the value is penalized if it goes above a certain ratio threshold...how is this penalization encoded (i.e., is it still a continuous function where the maximum value of the function is located at the target ratio, or is this a discontinuity whereby after the target ratio is reached, the state quality suddenly jumps to a lesser or negative value)? Hint: continuous is always better, oftentimes even required.
- You still keep referring to many of your choices as "incentivizing the AI to XXX", where XXX is something like "search through transfers instead of transforms"...this submission is much better than Part 1 at keeping your human intuition out of it, but it seems like you are still trying to push your AI to behave in a certain way and/or certain order. Remember, the purpose of AI is NOT to make the AI behave in the same way as a human...it's for it to come up with logical actions based on a desired goal/outcome. I know those two statements sound similar, but they're not saying the same thing. In your specific case, you shouldn't care at all HOW your agent ends up increasing its EU (i.e., what actions it takes in what order), the ONLY thing you are trying to do is to ensure that at the end of the day, your agent has come up with a world state that is "good" based on your state quality function. If you ever catch yourself thinking "I'd like to incentive my AI to ....", then whatever you're about to do is probably not going to have the intended effect and will also remove much of the "intelligence" part of the AI.
- I like your Greedy Best-First Search results...the shape of the outcome for the EU values seems reasonable (with some significant growth up front that seems to lead to diminishing returns later on). And your explanation of why GBFS tends to lead to higher EU values very quickly is spot-on.
- I also really enjoyed seeing the comparison of GBFS for your two country initial states...it was cool that they were both able to get up to similar final EU values although in very different ways...neat result and analysis. Your explanation of why you sometimes see big jumps in EU also makes sense to me based on the randomness of the trade percentage in your implementation. I actually think this is a good implementation detail (since it allows your AI to search different parts of the search space randomly without any guidance or intuition), and I think that if you had been able to continue searching to much deeper depths (like hundreds or thousands), this detail would have been a huge factor in ensuring that your AI is able to continue improving its EU pretty substantially over a significant period of time.
- In your "resource decay" explanation, you mention that it is tiered based on node count (and you mention many thousands of nodes in each tier). Why are you using node count for resource decay vs. node depth? If I'm correct in assuming that node count is equal to the number of nodes that have been added to the frontier, then I'm not sure that this metric makes sense...this would penalize actions that get added to the frontier at a later time, even if they are only ACTUALLY the second or third action that would be present in a schedule, for example. Resource decay shouldn't have to do with the length of your search, but rather the length of your schedule.
- Good analysis of the limitations of Heuristic-DFS, this is always problematic when using this search strategy on very large/infinite search spaces.
- I also like your analysis of the limitation of the Breadth-First Search strategy - from your results, it looks like it was JUST starting to begin an exponentially increasing growth rate in EU, so it would have been very interesting to see what EU values it was able to find if it could have searched to say a depth of 100 (vs. a similar depth using Greedy Best-First Search). You hit the nail on the head on why BFS is rarely used for problems like this with large branching factors, but nonetheless, BFS does guarantee that the actually optimal solution will be found (if you had infinite resources and time), so it's cool to compare these results to Greedy Best-First Search just to see how much of a tradeoff there is for gaining speed vs optimality.
- The little extra features you added to your agent are really cool (EcoWaste recycling, randomness of action choice, etc.)!
- One note, alpha-beta pruning definitely does NOT add human intuition to the agent. The only thing alpha-beta pruning does is to remove paths from the search tree that are GUARANTEED to be worse than something that has already been explored. And it does this in a mathematically sound way (with no knowledge of the meaning behind what it's doing).
- Very good explanation during your Test Cases summary. I think you've made a ton of progress in this course and especially since project Part 1. The only thing that you still try to do is to guide your AI in certain ways that aren't advisable, but I think you'll be able to overcome this with more exposure and practice. It's definitely not a natural thing to program in this way, but you've made GREAT progress!
- By the way, thank you so much for adding the links in the GitHub repo that go to specific areas in your code. This was super helpful to see exactly what you were referring to in your presentation.