Intelligent Systems Robots, Agents, and Humans
Intelligent Systems Robots, Agents, and Humans CAP 6671
University of Central Florida
Popular in Course
Popular in System Engineering
This 23 page Class Notes was uploaded by Khalil Conroy on Thursday October 22, 2015. The Class Notes belongs to CAP 6671 at University of Central Florida taught by Gita Sukthankar in Fall. Since its upload, it has received 43 views. For similar materials see /class/227212/cap-6671-university-of-central-florida in System Engineering at University of Central Florida.
Reviews for Intelligent Systems Robots, Agents, and Humans
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/22/15
CAP6671 Intelligent Systems Lecture 6 Trading Agent Competition Part 1 Instructor Dr Gita Sukthankar Email gitarseecsucfedu Schedule T amp Th 9001015am Location HEC 302 Office Hours in HEC 232 K T amp Th 1030am12 Why have TAC CAP6671 Dr Gita Sukthankar Why have TAC Standardize research problem Shopping agents are a useful class of personal assistant agents Auctions are a good decentralized mechanism for maximizing group utility CAP6671 Dr Gita Sukthankar What are the research problems CAP6671 Dr Gita Sukthankar What are the research problems Rapid optimizationsearch Auction bidding strategies Prediction Agent allocation Planning under uncertainty see next paper Learning models from past data Adversarial strategies CAP6671 Dr Gita Sukthankar History of TAC First competition was in 2001 organized by Michael Wellman Competitions are often held at AAAI or AAMAS 3 types of competition TAC Classic agents act as personal travel agents for a group of clients and attempt to maximize their clients utilities TAC Supply Chain Management agents manufacture PCs win customer orders procure components TAC Market Design reverse problem in which the organizers provide the agents and the competitors design markets CAP6671 Dr Gita Sukthankar Competition Rules 3 Agents 28 Auctions fquot Flight my markets RH F 39 3 Clients Hotel auc ong 6 l39wQ iEi Itertainment 5 exnhanges CAP6671 Dr Gita Sukthankar Game Design Game 8 agents competing in 15 minute games Agents are simulated travel agents with 8 clients Client needs to travel from TACtown to Boston and home again in a 5 day period Auctions for flight hotels and entertainment ticket Server maintains markets sends prices to agents Agents sends bids to server over network must be able to cope with network issues CAP6671 Dr Gita Sukthankar 28 Simultaneous Auctions Flights Inflight days 14 Outflight days 25 8 Unlimited supply immediate clear no resale Hotels 2 different hotels for days 14 8 16 rooms per auction 16th price ascending English auction no resale Due to delayed bidding it reduces to mprice sealed bid auction Random auction closes minutes 411 Entertainment Continuous double auction no trading phases prices to buy and sell may be submitted at any time Resale allowed CAP6671 Dr Gita Sukthankar Client Preferences Preferences randomly generated per client Ideal arrival departure days Good hotel value Entertainment values CAP6671 Dr Gita Sukthankar Agent Design Bidding offering payments for goods to gain utility Allocating Constructing travel packages for each of the 8 clients After auctions close agents have 4 minutes to report allocations of goods to clients Score difference between summed clients utilities and agents expenditure CAP6671 Dr Gita Sukthankar Game Structure Get market prices from server Decide on what goods to bid Decide at prices Decide for how many to bid Decide at what time to bid UNTIL game over Allocate goods to clients Uquot39gtSJquot39 l CAP6671 Dr Gita Sukthankar 12 Bidding Strategies Hotel auction Hotel rooms are limited resource Refrain from bidding early unless the auction seems near to closing One strategy Treat current holdings as sunk costs and calculate the utility of an unsecured hotel room reservation as the utility of the package marginal utility Bid this utility due to the structure of the munit auction the agent will pay less than the closing price CAP6671 Dr Gita Sukthankar Bidding Strategies Flight auction Delay bidding on flights until end of game In future versions of the competition the prices increased towards end of the game which made bidding earlier more advantageous Account for unpredictable network and server delays to make sure bid is received before the game is over Bid at maximum price to make sure that bids were not rejected because of information delays resulting from network asynchrony CAP6671 Dr Gita Sukthankar Bidding Strategies Entertainment auction Focus on obtaining complete packages or Separate the problem into calculating travel packages and entertainment packages separately and solving greedily Greedy strategy has problems If client doesn t have ticket to event then better to extend client stay when utility gain exceeds cost of ticket plus hotel plus travel penalities Similarly it can be better to shorten stay and sell off tickets CAP6671 Dr Gita Sukthankar Results from 2000 TAC Competition A39l39l39ac P Stone Roxybot J Boyan and A Greenwald Aster InterTrust Research Lab UMBCTAC UMBC hWNE How would you tackle the problem CAP6671 Dr Gita Sukthankar A39lTac Bidding Calculate G most profitable allocation of goods to clients based on current holdings and predicted future prices for use in bidding Buysell bids for entertainment based on a sliding price strategy dependent on time till end of game Allocation Uses MILP to find optimal allocation Online adaptation to game conditions Passiveactive bidding modes based on server latency Allocation strategy based on time required for MILP Hotel bidding based on closing prices in previous games CAP6671 Dr Gita Sukthankar RoxyBot Allocation Using an A search with admissible heuristic or variablewidth beam search Completer Optimal quantity of resources to buy and sell using priceline structure to forecast future costs Pricelines are learned using ML techniques whereas A39l39l39ac uses heuristics to estimate future prices CAP6671 Dr Gita Sukthankar Aster Heuristic bidding and locally optimal search for final allocation Bidding Delay precommit phase Bid for consecutive nights Calculate utility of other agents when doing entertainment bids CAP6671 Dr Gita Sukthankar UMBCTAC Allocation Consider agent itineraries individually rather than solving 8 client optimization problem Switch itineraries often early on and then avoid switching itineraries late in game Bidding Flights bid maximum price Hotels bid current price plus a price increment based on past transactions Entertainment Buy tickets if client is in town that night at market value Sell tickets at average of preference values 20 CAP6671 Dr Gita Sukthankar Observations No incentive to buy airline tickets early Hotel auctions were effectively sealedbid Only limited activity in entertainment auction Difficult to observe bidding pattern of individual agents CAP6671 Dr Gita Sukthankar 21 Research Problems in 2000 TAC How to estimate utility of current holdings How to calculate future prices Howwhen to bid Calculating final optimal allocation within time limits CAP6671 Dr Gita Sukthankar 22 Homework Reading A Greenwald and J Boyan Bidding under Uncertainty Theory and Experiments Proc of UAI CAP6671 Dr Gita Sukthankar 23
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'