Plan, Activity, and Intent Recognition This page is intentionally left blank Contents About the Editors�����������������������������������������������������������������������������������������������������������������������������������xi List of Contributors����������������������������������������������������������������������������������������������������������������������������� xiii Preface�������������������������������������������������������������������������������������������������������������������������������������������������xvii Introduction������������������������������������������������������������������������������������������������������������������������������������������xix PART PLAN AND GOAL RECOGNITION CHAPTER Hierarchical Goal Recognition�������������������������������������������������������3 1.1 Introduction 1.2 Previous Work .5 1.3 Data for Plan Recognition 1.4 Metrics for Plan Recognition 10 1.5 Hierarchical Goal Recognition 12 1.6 System Evaluation 23 1.7 Conclusion 30 Acknowledgments 31 References 31 CHAPTER Weighted Abduction for Discourse Processing Based on Integer Linear Programming��������������������������������������������������������33 2.1 Introduction .33 2.2 Related Work 34 2.3 Weighted Abduction 35 2.4 ILP-based Weighted Abduction 36 2.5 Weighted Abduction for Plan Recognition .41 2.6 Weighted Abduction for Discourse Processing 43 2.7 Evaluation on Recognizing Textual Entailment .47 2.8 Conclusion 51 Acknowledgments 52 References 52 CHAPTER Plan Recognition Using Statistical–Relational Models������������������57 3.1 Introduction .57 3.2 Background .59 3.3 Adapting Bayesian Logic Programs 61 3.4 Adapting Markov Logic 65 3.5 Experimental Evaluation 72 3.6 Future Work 81 3.7 Conclusion 81 v vi Contents Acknowledgments 82 References 82 CHAPTER Keyhole Adversarial Plan Recognition for Recognition of Suspicious and Anomalous Behavior����������������������������������������87 4.1 Introduction .87 4.2 Background: Adversarial Plan Recognition 88 4.3 An Efficient Hybrid System for Adversarial Plan Recognition 93 4.4 Experiments to Detect Anomalous and Suspicious Behavior 99 4.5 Future Directions and Final Remarks .115 Acknowledgments 116 References .116 PART ACTIVITY DISCOVERY AND RECOGNITION CHAPTER Stream Sequence Mining for Human Activity Discovery���������������������������������������������������������������������123 5.1 Introduction .123 5.2 Related Work 125 5.3 Proposed Model 129 5.4 Experiments 138 5.5 Conclusion 143 References .144 CHAPTER Learning Latent Activities from Social Signals with Hierarchical Dirichlet Processes����������������������������������������149 6.1 Introduction .149 6.2 Related Work 150 6.3 Bayesian Nonparametric Approach to Inferring Latent Activities 154 6.4 Experiments 160 6.5 Conclusion 171 References .172 PART MODELING HUMAN COGNITION CHAPTER Modeling Human Plan Recognition Using Bayesian Theory of Mind�����������������������������������������������������������177 7.1 Introduction .177 7.2 Computational Framework .181 7.3 Comparing the Model to Human Judgments 190 7.4 Discussion .195 7.5 Conclusion 198 References .198 Contents vii CHAPTER Decision-Theoretic Planning in Multiagent Settings with Application to Behavioral Modeling������������������������������������205 8.1 Introduction .205 8.2 The Interactive POMDP Framework 206 8.3 Modeling Deep, Strategic Reasoning by Humans Using I-POMDPs 210 8.4 Discussion .221 8.5 Conclusion 222 Acknowledgments 222 References .222 PART MULTIAGENT SYSTEMS CHAPTER Multiagent Plan Recognition from Partially Observed Team Traces��������������������������������������������������������������227 9.1 Introduction .227 9.2 Preliminaries 228 9.3 Multiagent Plan Recognition with Plan Library .230 9.4 Multiagent Plan Recognition with Action Models 235 9.5 Experiment 241 9.6 Related Work 246 9.7 Conclusion 247 Acknowledgment 248 References .248 CHAPTER 10 Role-Based Ad Hoc Teamwork���������������������������������������������������251 10.1 Introduction .251 10.2 Related Work 252 10.3 Problem Definition 255 10.4 Importance of Role Recognition .257 10.5 Models for Choosing a Role 258 10.6 Model Evaluation 263 10.7 Conclusion and Future Work 271 Acknowledgments 272 References .272 PART APPLICATIONS CHAPTER 11 Probabilistic Plan Recognition for Proactive Assistant Agents��������������������������������������������������������275 11.1 Introduction .275 11.2 Proactive Assistant Agent .276 11.3 Probabilistic Plan Recognition .277 11.4 Plan Recognition within a Proactive Assistant System 282 viii Contents 11.5 Applications 284 11.6 Conclusion 286 Acknowledgment 287 References .287 CHAPTER 12 Recognizing Player Goals in Open-Ended Digital Games with Markov Logic Networks������������������������������������������289 12.1 Introduction .289 12.2 Related Work 291 12.3 Observation Corpus 293 12.4 Markov Logic Networks 298 12.5 Goal Recognition with Markov Logic Networks 300 12.6 Evaluation .303 12.7 Discussion .306 12.8 Conclusion and Future Work 309 Acknowledgments 309 References .309 CHAPTER 13 Using Opponent Modeling to Adapt Team Play in American Football���������������������������������������������������������313 13.1 Introduction .313 13.2 Related Work 315 13.3 Rush Football 317 13.4 Play Recognition Using Support Vector Machines 319 13.5 Team Coordination 321 13.6 Offline UCT for Learning Football Plays .326 13.7 Online UCT for Multiagent Action Selection 330 13.8 Conclusion 339 Acknowledgment 339 References .339 CHAPTER 14 Intent Recognition for Human–Robot Interaction�������������������������343 14.1 Introduction .343 14.2 Previous Work in Intent Recognition 344 14.3 Intent Recognition in Human–Robot Interaction 345 14.4 HMM-Based Intent Recognition 348 14.5 Contextual Modeling and Intent Recognition 349 14.6 Experiments on Physical Robots 356 Contents ix 14.7 Discussion .363 14.8 Conclusion 364 References .364 Author Index�������������������������������������������������������������������������������������������������367 Subject Index�����������������������������������������������������������������������������������������������379 372 Author Index Katrenko, S., 49 Kautz, H.A., 6, 57–58, 71, 88, 91, 123, 125–126, 188–189, 227, 246–247, 254, 275, 291, 294 Kawashima, M., 343 Kawato, M., 190 Ke, Y., 127 Kelley, R., 345, 364 Kemp, C., 179, 181, 190 Kennedy, N., 151–152 Kersting, K., 58–60, 65, 67 Keshet, J., 42 Khalastchi, E., 89 Khawaja, F., 123 Khot, T., 67 Kim, K.-E., 189, 195 Kim, S., 151, 153 Kim, T., xxvi Kimmig, A., 80 Kimura, H., 345 King, C., 345 King-Casas, B., 211, 215 Kivelä , M., 153 Kjærulff, U., 90 Knill, D., 181 Knoblock, C.A., 276 Knox, W., 315 Kocsis, L., 326 Koedinger, K.R., 309 Kok, S., 67, 81 Kok, S., 73 Koller, D., 60, 66, 72, 79, 90, 189 Kollingbaum, M.J., 275 Konik, T., 318 Konolige, K., 346 Koós , O., 177 Koos, R., 291 Kovacic, S., 315 Kowalski, R.A., 59 Kraemer, L., 227, 230, 241, 247 Krasnow, M.M., 196 Kraus, S., 251–254 Krose, B., 125–126 Kuhlmann, G., 315 Kullback, S., 324 Kumar, M., 152, 163 Kumpula, J.M., 153 Kuno, Y., 343 Kuris, B., 151 Kuter, U., 4, Kuzuoka, H., 343 Kwan Shan, M., 127 Kwapisz, J.R., 151 Kwatra, N., 88, 129 L Lafferty, J.D., 91, 189, 300 Lai, P., 190 Laird, J., 339 LaMarca, A., 152 Lane, N.D., 151 Lane, T., 89 Langley, P., 318 Lapata, M., 45 Larimer, N., 130 Larson, K., 123, 125–126 Lasecki, W., 125 Laviers, K., 291, 323, 325–326, 333 Lee, S., 151, 153, 291, 302, 306–307, 309 Lee, S.M., 190 Lee, S.Y., 292 Lee, W.S., 127, 184 LeGrand, L., 152 Leibler, R., 324 Lepri, B., 153 Lerman, K., 255, 276 Lesh, N., Lesh, N., 57 Lesser, V.R., 253 Lester, J., 291–292, 296–297, 302, 306–307, 309 Levesque, H.J., 59 Levinson, R., 291 Lewis, D., 188 Lewis, M., 284 Li, C.M., 228–229, 240 Li, L., 228, 245, 247, 254 Li, M., 151, 153, 253 Li, N., 318 Liao, L., 6, 88, 91, 123, 125–126, 189 Lieberman, J., 345 Liemhetcharat, S., 253 Lim, J., 316 Lin, 89, 320 Lisy, V., 93, 116 Litman, D.J., 188, 227 Littman, M.L., 151, 179, 183, 195, 205 Litvin, A., 123 Liu, B., 134 Liu, Z., 151 Lo, B., 152 Long, J., 87–88, 90 Lopez, A., 318 Lorincz, K., 126, 151–152 Lovejoy, W.S., 185–186 Lovell, N.H., 152 Author Index Lowd, D., 73 Lowd, D., 58, 60–61, 71 Lu, H., 151–152 Lu, J., 125–126, 128 Lucas, C.G., 190 Luck, M., 284 Lukowicz, P., 126 Lunt, T., 90 Luo, Y., 177 Lyle, J., 227, 230, 241, 247 M Ma, Y., 134 Macindoe, O., 181, 190, 195 MacQueen, J.B., 156 Maentausta, J., 151 Maglogiannis, I., 152 Magnini, B., 48–49 Mahadevan, S., 57, 247 Mahajan, D., 88, 129 Maisonnasse, J., 125–126 Majumdar, A., 316 Malan, D.J., 126 Manku, G.S., 127 Manning, C.D., 165 Mansinghka, V.K., 190 Manya, F., 228–229, 240 Mao, W., 92 Marascu, A., 127, 129 Marcu, D., 308 Mardenfeld, S., 153 Marhasev, E., 90–91 Markert, K., 48 Marr, D., 181, 197 Marsella, S., 92, 180, 189–190, 211, 316 Martin, P., 33–35, 39, 57 Masato, D., 247, 275 Masseglia, F., 127, 129 Mataric, M., 255, 258 Matsuo, Y., 34 Maurer, U., 125–126 Mayora, O., 152 Mazziotta, J., 343, 350 McCall, Joel C., 102 McCarragher, B., 345 McCarthy, G., 190 McCarthy, J., 315 McCord, M., 33–34, 48, 50–52 McCracken, P., 253 McDermott, D., 57 McDermott, J., 276 McGrath, M.J., 151 McKelvey, R., 210, 215–216 McQuiggan, S., 296 Mead, R., 218 Mehrotra, S., 276–277, 284, 286 Meijering, B., 206 Meissner, C., 221 Meltzoff, A.N., 177, 190 Meneguzzi, F., 275–278, 282–284, 286 Merdler, E., 100 Mertens, J., 207 Meyers, C., 221 Michahelles, F., 126 Milch, B., 187, 189 Miller, C.A., 57, 189 Miller, G.F., 190, 195–196 Minton, S., 276 Mitchell, T.M., 6, 276 Mitra, U., 151, 153 Mohamedou, N., 228, 240 Moldovan, D., 48 Molineaux, M., 319, 323, 325 Molnar-Szakacs, I., 343, 350 Montague, P., 211, 215 Montazeri, N., 33–34, 48, 50–52 Montemerlo, M., 177 Mooney, R.J., 33–34, 41–43, 48, 50, 52, 57–59, 71–73, 79, 81, 246, 294 Moore, A., 343 Moore, S.A., 151 Mortazavi-Asl, B., 127 Mortensen, E., 316 Moses, Y., 188 Mott, B., 291–292 302, 306–307, 309, 291–292, 306–307, 309 Motwani, R., 127 Mudda, S., 152 Muggleton, S., 80–81 Mukherjee, J., 316 Mulkar, R., 34, 42 Mulkar-Mehta, R., 33–34, 48, 50–52 Müller, P., 156 Munguia-Tapia, E., 123, 126 Murdock, J.W., 4, Murphy, 185 Murphy, K.P., 14 Murray, W., 51 Muslea, M., 276 Myers, K., 90 Myllymäki, P., 81 Mynatt, E., 123, 149 Mysore, P., xxi, 151 373 374 Author Index N Nádasdy, Z., 177–178, 190 Nair, R., 316 Nakashima, H., 316 Narayanan, M., 152 Naroska, E., 129 Natarajan, S., 67, 71, 276 Nau, D., 4, Nawoj, A., 126 Neal, R.M., 156 Nelder, J.A., 218 Nelson, J., 151–152 Neu, G., 189, 195 Nevatia, R., 90 New, J., 196 Ng, A.Y., 150, 163, 189, 195, 278 Ng, B., 221 Ng, H.T., 34, 41, 43, 57–59, 72, 73 Ng, W., 127 Ngo, L., 58, 70 Nguyen, N., 91 Nguyen, T., 129 Nichols, J., 319 Nicholson, A., 295 Nicholson, A.E., 6, 11, 57, 189, 195 Nicklas, D., 149 Nicolai, T., 153 Nicolescu, M., 345, 364 Niles, I., 48 Nilsson, D., 65, 74 Nilsson, N.J., 227–229 Nitao, J., 221 Niu, W., 87–88, 90 Noda, I., 316 Norman, T.J., 247, 275–278, 282–284 Norvig, P., 14, 278 Novischi, A., 48 Nutt, J., 130 O Ogawara, K., 345 Ogris, G., 126 Oh, J., 275–278, 282–284, 286 Ohya, J., 91 Okazaki, N., 42 Olguín, D.O., 151 Olguín, DO., 151, 160 Oliveira, A.L., 81 Oliver, N., 30, 91 Oltramari, A., 45 Ong, I., 67 Ong, S.C.W., 184 Onishi, K.H., 177, 190, 197 Orkin, J., 291, 295 Ormoneit, D., 189 O’Shea, T.J., 151 Ossowski, S., 284 Ovchinnikova, E., 33–34, 45, 47–48, 50–52, 57 Ozono, H., 196 Ozsecen, Y.M., 152 Oztop, E., 190 P Padasdao, B., 152 Paek, T., 3, 57 Page, D., 67 Palfrey, T., 210, 215–216 Palla, G., 153 Pallavi, V., 316 Palmes, P., 129 Pan, J.J., 126 Pantel, P., 33 Pantelis, P.C., 195 Papadopoulos, A., 152 Parker, J., 315–316 Paskin, M.A., 14 Patel, S., 126, 151–152 Patterson, D.J., 6, 125–126, 129 Pauli, J., 129 Pavel, M., 130 Pearl, J., 58, 60, 65, 67, 79 Pechoucek, M., 93, 116 Pei, J., 125, 127, 129, 131–132, 137–138 Penas, A., 33–34, 52 Peng, Y., 59 Pennacchiotti, M., 45 Pentland, A., 30, 91, 126, 150–151, 153, 159, 165 Perera, A., 291 Perkowitz, M., 125–126, 129 Perner, J., 179 Perrault, C.R., 188 Perrault, R., 181 Pers, J., 315 Peterson, G.L., 221 Peterson, K., 278 Petruck, M., 33–34, 45 Pfeffer, A., 189, 206, 210, 215 Phan, H., 91, 151 Philipose, M., 125–126, 129 Phun, D., 91, 129, 151–152, 163 Phung, D., 149, 152 Author Index Phung, D.Q., 87–88, 90–91 Pibil, R., 93, 116 Pietra, S.D., 300 Pietra, V.D.P., 300 Pines, Z., 315–316 Pinkal, M., 45 Pino, E.J., 126 Pinto, H., 127 Pioggia, G., 152 Pitman, J., 156 Plagianakos, V.P., 152 Planes, J., 228–229, 240 Plantevit, M., 127 Png, S.W., 184 Poncelet, P., 127, 129 Pook, P., 345 Poole, D., 34, 57–58, 80–81 Poon, H., 72, 74, 76 Poon, H., 73 Pople, H.E., 59 Prakken, H., 284 Pratap, R., 315–316 Premack, D., 343 Puiatti, A., 152 Pung, H., 125–126, 128 Pung, H.K., 129 Pynadath, D.V., 3, 5, 57, 91–93, 180, 189, 211, 227, 276, 293 Q Qu, X., 180, 189, 195, 210, 214, 216, 221, 316 Quartz, S., 215 R Rabbi, M., 152 Rabiner, L.R., 186, 345 Raghavan, P., 165 Raghavan, S., 33–34, 73 Raines, T., 316 Raïssi, C., 127, 129 Ramachandran, D., 189 Ramanujam, K., 315–316 Ramíez, M., 275, 278 Ramirez, M., 180, 227, 246, 293 Ramírez, M., 278 Ranganathan, A., 149 Rao, R., 190 Rao, S., 123 Rashidi, P., 123–126, 128–131, 133, 135–136, 151 Rastogi, R., 127 Rathnasabapathy, B., 209 Ratliff, N., 278 Ravi, N., 151 Ray, D., 211, 215 Redmond, S.J., 152 Reggia, J.A., 59 Reignier, P., 125–126 Reyle, U., 44 Rich, C., Richards, W., 181 Richardson, M., 73 Richardson, M., 48, 60, 65, 292, 300, 303 Riedel, S., 40, 72, 74, 301, 305 Riedl, M.O., 291 Rijn, H.V., 206 Riley, P., 315 Rissanen, J., 136 Rist, T., 316 Rizzolatti, G., 343, 350 RJ, Kate, 34, 65–66 RM, MacGregor, 33 Robison, J., 296 Rocha, R., 80 Roos, T., 81 Rosario, B., 30 Rosenbloom, P.S., 87, 92, 110, 112–113, 115 Rosenschein, J.S., 251–252 Rosenthal, R., 211 Rosso, R., 152 Roth, D., 48–49 Rowe, J., 296–297 Rowlands, D., 126 Roy, D., 291, 295 Rubin, D.B., 155, 161 Ruppenhofer, J., 33–34, 45 Russell, S., 14, 189, 195, 278 Russmann, H., 126 Rusu, R.B., 346 S Sadilek, A., 6, 58, 71, 227, 247, 254, 294 Salarian, A., 126 Sánchez, D., 125–126 Sanik, K., 195 Santos Costa, V., 80 Santos, E., 34, 39 Santos, J., 80–81 Saramäki, J., 153 Saretto, C.J., 291 Saria, S., 57, 247 Sarrafzadeh, M., xxv, 128 375 376 Author Index Sato, T., 80–81 Saxe, R., 181, 190, 195, 197, 211, 275, 278 Scanaill, C.N., 151–152 Schaeffer, J., 326 Schank, R.C., 188 Schiele, B., 125–126, 129, 151, 153, 163 Schmid Mast, M., 152 Schmidt, C.F., 188, 190, 227, 291, 296 Schmidt, K., 215 Schmitter-Edgecombe, M., 123–126, 129, 130, 133, 135–136 Scholl, B.J., 190 Schultz, J., 190 Schultz, T.R., 190 Schütze, H., 165 Searle, J.R., 179, 188 Sergot, M., 284 Sethuraman, J., 156 Seymour, B., 190 Seymour, R., 221 Shafer, G., 18 Shafto, P., 181, 190 Shalev-Shwartz, S.Y.S., 42 Shaogang, G., 88, 90 Shapiro, D., 318 Shavlik, J., 67, 71 Shen, D., 45 Shih, E.I., 126 Shimony, S.E., 34 Shipman, W., 34 Shnayder, V., 126 Shon, A.P., 190 Shultz, T.R., 190 Shunjing, J., 123 Si, M., 189 Sidner, C.L., 188 Siewiorek, D., 125–126 Sikka, P., 345 Silver, D., 331 Simmel, M.A., 190 Singer, Y., 91, 96, 307 Singla, P., 73 Singla, P., 33, 41–43, 71–73, 79, 81, 246, 294 Sisi, Y., 123 Smailagic, A., 125–126 Smallwood, R., 205 Smith, S., 276 Sondik, E., 205 Song, Y., 125, 291 Sorensen, G., 254 Spada, H., 190 Spronck, P., 315 Spruijt-Metz, D., 151, 153 Squire, K., 292 Sridharan, N.S., 188, 227, 291, 296 Srikant, R., 127 Srinivasa, S., 278 Stahl, D.O., 189, 210 Starner, T., 6, 91 Stauffer, C., 126 Stavens, D., 177 Steedman, M., 91, 275 Stentz, A.T., 253 Stern, H.S., 155, 161 Steyvers, M., 190 Stiborek, J., 93, 116 Stickel, M., 33–35, 39, 57 Stiefmeier, T., 126 Stone, P., 251–254, 315–316, 320 Stracuzzi, D., 318, 345 Struyf, J., 67 Stuhlmüller, A., 190 Sukthankar, G., 92, 125, 128, 227, 247, 254, 291, 316, 319–320, 323, 325–326, 333 Sukthankar, R., 125, 128 Sumner, M., 73 Sural, S., 316 Susan Pan, J., 153 Suter, D., 151 Sutton, R.S., 189 Suzic, R., 92 Swami, A., 127 Sycara, K., 92, 227, 247, 254, 275–278, 282–284, 286, 316, 320 Szepesvári, C., 189, 195, 326 T Taatgen, N., 206 Tadepalli, P., 67, 276 Tagliarini, G.A., 34 Takamatsu, J., 345 Tambe, M., 57, 87, 90, 92–93, 110, 112–113, 115–116, 227, 253, 316, 320 Tanaka, K., 316 Tanaka-Ishii, K., 316 Tao, X., 125–126, 128 Tapia, E.M., 123, 125–126 Tartarisco, G., 152 Taskar, B., 303 Tasoulis, S.K., 152 Tatu, M., 48 Tauber, S., 190 Tavakkoli, A., 345 Teh, Y.W., 150, 156–159, 161 Teisseire, M., 127, 129 Author Index Tenenbaum, J.B., 275, 278 Tenenbaum, J.B., 92, 179, 181, 190, 195, 211 Teng, W.-G., 127 Tentori, M., 125–126 Thater, S., 45 Thompson, J., 51 Thonnat, M., 88, 90 Thrun, S., 177, 344 Tian, Q., 316 Tierney, M., 151–152 Tishby, N., 91, 96 Tittle, J., 276–277, 284, 286 Todd, P.M., 190, 195–196 Todorov, E., 189, 195 Toledo, A., 49 Tolkiehn, M., 152 Tomlin, D., 215 Toni, F., 59 Tooby, J., 196 Tran, K., 152, 163 Tremoulet, P.D., 190 Trivedi, Mohan M., 102 Troster, G., 126 Trucco, E., 346 Truxaw, D., 196 Tsay, I.A., 130 U Ullman, T.D., 181, 190, 195 Uono, S., 196 V Vahdatpour, A., 128 Vail, D.L., 91, 189 Valls, J., 318 Valtonen, M., 151 van Kasteren, T., 125–126 Van Overwalle, F., 190 vanden Herik, J., 315 Vanhala, J., 151 VanLehn, K., 291 Vapnik, V., 319 Vardi, M.Y., 188 Vasconcelos, W.W., xxii, 247 Vaswani, N., 151 Veloso, M.M., 91, 189, 253, 315, 320 Venkatesh, S, 14, 57, 87–88, 90–91, 129, 151–152, 163, 189 Verbrugge, R., 206 Verma, D., 190 Verri, A., 346 VI, Morariu, 184 Vicsek, T., 153 Vieu, L., 45 Vingerhoets, F., 126 Vinterbo, S.A., 126 Voelz, D., 316 VSN, Prasad, 184 W Wagner, A.Z., 309 Wah, B.W., 127 Wahl, S., 190 Walker, S.G., 156 Wang, J., 127 Wang, L., 128, 151 Wang, S.H., Wang, W., 125, 127 Wang, X., 128 Wang, Y.-F., 87–88, 90 Ward, C.D., 326 Ward, J., 275, 278 Watanabe, Y., 42 Waterman, J., 126 Waugh, K., 189 Weigelt, K., 189 Weinstein, A., 195 Weiss, G.M., 151 Wellman, H.M., 177, 190, 197 Wellman, M.P., 3, 5, 57, 59, 70, 91, 189, 293 Welsh, M., 126 West, G, 14, 57, 91, 189 West, M., 159 Wigand, L., 364 Wilensky, R., 227 Wilson, P., 210 Wilson, P.W., 189 Wimmer, H., 179 Wolpert, D., 190 Wood, 221 Woodruff, G., 343 Woodward, 177, 221 Wray, R., 339 Wren, C., 123, 126 Wu, C., 195 Wu, D., 4, Wu, F., 253 Wu, G., 87–88 Wu, K., 228 Wu, X., 129 Wu, Y., 87–88 Wu, Z., 125–126, 128 377 378 Author Index Wyatt, D., 129 Wynn, K., 177, 190 X Xiang, T., 90 Xu, C., 316 Xu, F., 190 Xue, W., 129 Y Yamamoto, K., 42 Yamato, J., 91 Yamazaki, A., 343 Yamazaki, K., 343 Yan, X., 125, 127, 129, 131–132, 137–138 Yang, G.Z., 152 Yang, J., 151 Yang, Q., 91, 126, 228, 293 Yannakakis, G., 291 Yin Lee, S., 127 Yin, J., 126 Yiping, T., 123 Yiu, T., 127 Yoshida, W., 190 Young, D.L., 180, 189, 210, 212, 214, 216, 221 Young, R.M., 291 Youngblood, M., 123 Yu, C.J., 40 Yu, P., 125, 127, 129, 131–132, 137–138 Z Zabowski, D., 276 Zacks, J.M., 190, 195 Zaki, M.J., 127 Zamir, S., 207 Zettlemoyer, L.S., 187 Zhang, J., 206, 210, 228 Zhang, Z., 152 Zhao, L., 125, 128 Zhongyuan, Y., 123 Zhu, X., 129 Zhuo, H.H., 228, 245, 247, 254 Ziebart, B., 189, 278 Zilberstein, S., 195, 205, 253 Zukerman, I., 6, 11, 57, 189, 195, 295 Subject Index A Abduction inference, 33 cost-based approaches, 34 grounding-based approaches, 34 probabilistic approaches, 34 AbductionBALP, 62 Abductive model construction, 70 Abductive Stochastic Logic Programs (ASLPs), 80 Abstract Hidden Markov Model (AHMM), 5, 14 ACCEL system, 43, 72–73 Activity modeling, 344 Activity recognition, 123, 151 activity annotation, 126 activity data, 126 activity models, 126 and intent recognition, 349 pervasive sensor-based, 152 Actuators, 347 Ad hoc agents/teammates best-suited model, determining, 264 Capture-the-Flag domain, 254 evaluation of model, 263 foraging domain, 254 incremental value model, 261 limited role-mapping model, 260 measure of marginal utility, 252 multiagent plan recognition, 254 multiagent teamwork, 253 predictive modeling, 268 unlimited role-mapping model, 259 Advanced Scout system, 316 Adversarial plan recognition, 87 air-combat environment, 112 anomalous behavior, detecting, 99 AVNET consortium data, 108 catching a dangerous driver, 112 CAVIAR data, 101 efficient symbolic plan recognition, 95 efficient utility-based plan recognition, 96 hybrid system for, 93 suspicious behavior, detecting, 110 Air-combat environment, 112 aggressive opponent, 114–115 coward opponent, 94 Ambient sensors, 123 additional sensors, 126 in smart environments, 124 American football, 314–315, 317 Anomalous behavior, detecting, 99 AVNET consortium data, 108 CAVIAR data, 101 learning algorithm, 100 Anomalous plan recognition, 88 keyhole adversarial plan recognition for, 87 Anytime Cognition (ANTICO) architecture, 276 Appearance-based object recognition, 346 Artificial corpus generation, domain modeling, goal generation, planner modification, start state generation, Augmented forward probabilities, 16 Automatic subgroup detection, 323 AVNET data, 99, 108 percentage of false positives in, 108 standing for long time on, 109 U-turn on, 109 B Backward chaining, 35–36 Basic probability assignment (bpa), 18 combining evidence, 20 complexity, 20 focal elements of, 18 prediction, 20 Bayesian Abductive Logic Programs (BALPs), 59 Bayesian logic programs (BLPs), 60 adapting, 61 logical abduction, 61 probabilistic modeling, inference, and learning, 64 Bayesian mixture modeling with Dirichlet processes, 154 Bayesian nonparametric (BNP) methods, 150 Bayesian theory of mind (BToM), 179, 181 AI and ToM, 188 alternative models, 187 formal modeling, 183 informal sketch, 181 Behavioral modeling, 206, 210 Belief–desire inference, 181, 186 Bellman equation, 279 Bigram model, 305 Binary decision diagrams (BDDs), 80 379 380 Subject Index C Candidate activities, 238 Candidate hypothesis, 35 Candidate occurrences, 232 Capture-the-Flag domain, 254, 292 Cascading Hidden Markov Model (CHMM), 13 algorithm overview, 15 complexity, 17 computing the forward probability in, 15 HHMMs, comparison to, 14 predictions, 17 schema recognition algorithm, 16 training, 16 Causal-link constraints, 239 CAVIAR data, 101 detecting time for, 106 image sequence in, 102 precision and recall on, 104 trajectories of, 103 Chinese restaurant process, 156–157 Cognitive modeling, 177, 190 Commonsense psychology, 188 Commonsense theory of mind reasoning, 178 Conditional completeness, 241 Conditional soundness, 241 Conjunctive normal form (CNF) formula, 229 Constraints hard, 233, 239 soft, 232, 239 solving, 234, 240 Context Management Frame infrastructure, 152 Context model, 354 Contextual modeling and intent recognition, 349 dependency parsing and graph representation, 351 graph construction and complexity, 352 induced subgraphs and lexical “noise,” 352 inference algorithm, 355 intention-based control, 356 lexical directed graphs, 350 local and global intentions, 350 using language for context, 351 Cost function, 35 Crystal Island, 291, 293–297, 300, 307 Cutting Plane Inference (CPI), 40, 299 CPI4CBA algorithm, 40 D DARE (Domain model-based multiAgent REcognition), 228 algorithm, 237 MARS and, 244 properties of, 240 Data cubing algorithm, 127 Decision-theoretic planning Bayesian belief update, 208 interactive POMDP (I-POMDP) framework, 206 Dempster-Shafer Theory (DST), 18 evidence combination, 19 Digital games goal recognition in, 289 Dirichlet process, 156 Dirichlet process mixture (DPM) model, 154 Dynamic Bayes Network (DBN), 5, 185 Dynamic Hierarchical Group Model (DHGM), 227 Dynamic play adaptation, 325–326 Dynamic Bayesian networks (DBNs), 90 E EA Sports’ Madden NFL® football game, 319 Electrocardiogram (ECG), 152 Expected cost, 91 F Factored-MLN model, 306 Finitely nested I-POMDP, 207 First-order linear programming (FOPL), 40 Folk–psychological theories, 177 Foraging domain, 254 Foreground–background segmentation, 346 FrameNet, 47 FREESPAN, 127 G Galvanic skin response (GSR), 152 Game telemetry, 290 Game-based learning environments, 290 Gaussian mixture models (GMM), 149 Geib and Goldman PHATT algorithm, 292 Generalized Partial Global Planning (GPGP) protocol, 253 Goal chain, Goal parameter value generation, Goal recognition, 3, 280, 289 adding parameter recognition, 17 hierarchical plan of, and Markov logic networks (MLNs), 300–301 n-gram models, 304 observation corpus, 293 representation of player behavior, 300 Goal schema generation, Subject Index Goal schemas, 12 GSP algorithm, 127 H Hard constraints, 233, 239 Healthcare monitoring pervasive sensors for, 152 Hidden Cause (HC) model, 65, 67, 292 Hidden Markov Models (HMMs), 91, 149, 186–187 based intent recognition, 344–345, 348, 356 coupled, 91 factorial, 91 layered, 91 recognition, 349 training, 348 Hidden predicates, 301 Hidden Semi-Markov Models (HSMMs), 91 Hierarchical Dirichlet processes (HDP), 129, 150, 157 Hierarchical goal recognition, 4, 12 goal schema recognition, 13 problem formulation, 13 Hierarchical Hidden Markov Model (HHMMs), 14, 96 Hierarchical parameter recognition, 21 Hierarchical transition network (HTN), 73 Household setting, 356 Human activity discovery, stream sequence mining for, 123 activity recognition, 123 ambient sensors, 123 mining activity patterns, 133 sequence mining, 127 stream mining, 127 tilted-time window model, 131 updating, 137 Human dynamics and social interaction, 152 Human plan corpora general challenges for, goal-labeled data, plan-labeled data, unlabeled data, Human plan recognition, modeling AI and ToM, 188 alternative models, 187 comparison to human judgments, 190 formal modeling, 183 informal sketch, 181 using Bayesian theory of mind, 177, 181 Humanoid robot experiments, 361 Human–robot interaction (HRI), 343 activity recognition and intent recognition, 349 actuators, 347 application to intent recognition, 353 dependency parsing and graph representation, 351 experiments on physical robots, 356 graph construction and complexity, 352 hidden Markov models (HMMs)-based intent recognition, 348 induced subgraphs and lexical “noise,” 352 inference algorithm, 355 in robotics and computer vision, 345 intention-based control, 356 lexical directed graphs, 350 local and global intentions, 350 processing camera data, 346 sensors, 346 training, 348 using language for context, 351 Hybrid adversarial plan-recognition system, 94 I Incremental value model, 261 Inference algorithm, 355 Inference-based discourse processing, 33 Input-Output Hidden Markov Models (IOHMM), 293 Instantiated goal recognition, 4, 12 Integer linear programming (ILP) techniques, 33 based weighted abduction, 36 cutting plane inference, 40 handling negation, 40 Intent recognition, 344 inference algorithm, 355 in robotics and computer vision, 345 intention-based control, 356 outside of robotics, 344 Intention model, 354 Intention-based control, 356, 360 Interaction modeling, 346 Interactive partially observable Markov decision process (I-POMDP) framework, 205–206, 316 Bayesian belief update, 208 computational modeling, 214 finitely nested, 207 learning and decision models, 215 level recursive reasoning, 211 solution using value iteration, 209 weighted fictitious play, 216 Inverse optimal control, 189, 278 IRL See Inverse optimal control ISAAC, 316 J J.48 classifier, 335 381 382 Subject Index K K-clique, 153 Key sensors, 134 Keyhole recognition, 88 Kinect, 346 K-means, 149 Knexus Research, 317 Knowledge base model construction (KBMC) procedure, 57, 70 Knowledge-lean approach, 307 Kullback-Leibler divergence, 323 L Last subgoal prediction (lsp) bpa, 23 Latent activities, 149 activity recognition systems, 151 Bayesian mixture modeling with Dirichlet processes, 154 healthcare monitoring, pervasive sensors for, 152 hierarchical Dirichlet process (HDP), 157 human dynamics and social interaction, 152 pervasive sensor-based activity recognition, 152 reality mining data, 165 sociometric data, 160 from social signals, 149 Latent Dirichlet allocation (LDA), 149–150 Lexical directed graphs, 350 dependency parsing and graph representation, 351 graph construction and complexity, 352 induced subgraphs and lexical “noise,” 352 using language for context, 351 Lexical noise, 352 Lexical-digraph-based system, 361 Limited role-mapping model, 260 Linux data, 73 M Macro-average, 305 Madden NFL® football game, 319 Markov Chain Monte Carlo methods, 154 Markov decision process (MDP), 5, 276 definition, 279 partially observable MDP, 276 representing user plan as, 278 Markov jump process, 153 Markov Logic Networks (MLNs), 58, 60, 290, 298–299, 303 abductive model construction, 70 adapting, 65 goal recognition and, 300–301 Hidden Cause Model, 67 Pairwise Constraint Model, 65 plan recognition using manually encoded MLNs, 71 player behavior, representation of, 300 probabilistic modeling, inference, and learning, 72 Markov network (MN), 298 Markov random field See Markov network (MN) MARS (MultiAgent plan Recognition System), 228 algorithm, 231 completeness of, 235 generated clauses, 243 properties of, 235 MA-STRIPS, 230 Maximum a posteriori (MAP) assignment, 60 MAX-SAT problem, 228 MaxWalkSAT, 299 Mental problem detection, 152 Mercury, 152 Micro-average, 305 Microsoft’s Kinect, 346 Minecraft, 290 Mining activity patterns, 133 Mini-TACITUS system, 50 Mixture modeling, 154 Model-selection methods, 155 Monroe dataset, 73 Monroe Plan Corpus, 10 Monte Carlo search algorithms, 326 tree search process, 318 Multiagent Interactions Knowledgeably Explained (MIKE) system, 316 Multiagent learning algorithms, 313 Multiagent plan recognition (MAPR), 57, 227 candidate activities, 238 candidate occurrences, 232 DARE algorithm, 237 hard constraints, 233, 239 MARS algorithm, 231 problem formulation, 230, 236 soft constraints, 232, 239 solving constraints, 234, 240 with action models, 235 with plan library, 230 Multiagent STRIPS-based planning, 229 Multiagent team plan recognition, 254 Multiagent teamwork, 253 Multiclass SVM, 320 Multilevel Hidden Markov Models, Multi-User Dungeon (MUD) game, Mutual information (MI), 324 Subject Index N Naive Bayes, 149 Narrative-centered tutorial planners, 307 Natural language, understanding, 33 Natural tilted-time window, 131 Next state estimator, 331 n-gram models, 304 NoObs, 188 O Norm assistance, 284 Observation bpa, 22 Observation constraints, 239 Observed predicates, 301 Offline UCT for learning football plays, 326 Online inferences, 191, 193 Online UCT for multiagent action selection, 330 method, 331 reward estimation, 336 successor state estimation, 335 UCT search, 333 Open-ended games, 290 Opponent modeling, 313 automatic subgroup detection, 323 dynamic play adaptation, 325–326 offline UCT for learning football plays, 326 online UCT for multiagent action selection, 330 play recognition using support vector machines, 319, 321 reward estimation, 336 Rush football, 317 successor state estimation, 335 team coordination, 321 UCT search, 333 Overmerging, 46 argument constraints, 46 compatibility constraints, 47 P Pacman Capture-the-Flag environment, 263 Pairwise Constraint (PC) model, 65 Parameter recognition, 17 adding, 17 hierarchical, 21 top-level, 17 Partially observable Markov decision processes (POMDP), 179, 183, 185, 195, 205 interactive, 206 modeling deep, strategic reasoning by humans using, 210 Passive infrared sensor (PIR), 123 Patrol robot, 357, 359–360 Pervasive sensor based activity recognition, 152 for healthcare monitoring, 152 PHATT algorithm, 93, 292 Physical robots, experiments on, 356 general concerns, 362 household setting, 357 intention-based control, 360 lexical-digraph-based system, 361 similar-looking activities, 359 surveillance setting, 356 Pioneer 2DX mobile robot, 356 Pioneer robot experiments, 361 Plan, activity, and intent recognition (PAIR), 180–181, 189–190 Plan corpora general challenges for, goal-labeled data, human sources of, plan-labeled data, unlabeled data, Plan decomposition path, 95 Plan library, 89 Plan recognition, 3, 275 abductive model construction, 70 adapting, 61, 65 applications, 284 artificial corpus generation, as planning, 278 assistive planning, 283 Bayesian logic programs (BLPs), 60 cognitively aligned plan execution, 283 data for, datasets, 72 emergency response, 285 goal recognition, 280 hidden cause model, 67 human sources of plan corpora, Linux data, 73 logical abduction, 59, 61 Markov Logic Networks, 60 metrics for, 10 Monroe dataset, 73 norm assistance, 284 Pairwise Constraint model, 65 plan prediction, 281 predicted user plan, evaluation of, 283 proactive assistant agent, 276, 282 probabilistic modeling, inference, and learning, 64, 72 representing user plan as MDP, 278 using manually encoded MLNs, 71 using statistical–relational models, 57 383 384 Subject Index Plan recognition See also Multiagent plan recognition (MAPR) Play recognition using support vector machines, 319, 321 Play recognizer, 331 Player behavior, representation of, 300 Player-adaptive games, 289–290 Point cloud, 346–347 Position overlap size, 101 Prediction score, 213 PREFIXSPAN, 127 Proactive assistant agent, plan recognition for, 276, 282 Probabilistic context-free grammars (PCFGs), Probabilistic plan recognition, for proactive assistant agents, 275 Probabilistic state-dependent grammars (PSDGs), Probabilistic Horn abduction (PHA), 58 Problem-solving recognition, 30 Propositional attitudes, 179 Pruning types of, 140 PSP algorithm, 127 PsychSim, 211 Q Quantal-response model, 210, 216 R Radial basis function (RBF) kernel, 319 Radio frequency identification (RFID), 149 Range image, 346 Rao-Blackwellization (RB), Rationality error, 213 Reality mining, 165 Reality Mining dataset, 153 Real-time strategy (RTS) games, 292 Recognizing Textual Entailment (RTE) task, 47 challenge results, 50 Reinforcement learning (RL) algorithm, 319 RESC plan-recognition algorithm, 112 Restaurant Game, 293 Reward estimator, 331 “Risk-sensitive” plan repair policies, 339–340 Robocup research, 316 Robocup simulation league games, 315 Robocup soccer domain, 318 Robotic systems, 177 Role-based ad hoc teamwork See Ad hoc agents/teammates Rush 2008 Football Simulator, 314, 318, 338 Rush Analyzer and Test Environment (RATE) system, 314, 338 Rush football, 315, 317 Rush play, 318 Rush playbook, 318 Rush simulator, 331 S Sandbox games, 290 Search-space generation, 37 Sensor map, 139 Sensors, 346 processing camera data, 346 Sequence mining, 127 SharedPlans protocol, 253 Shell for TEAMwork (STEAM) protocol, 253 Shrinkage effect, 157 Simplified-English Wikipedia, 352 Smart environments activity data in, 126 ambient sensors in, 124 Smoothing distribution, 187 Soft constraints, 232, 239 Sony PTZ camera, 356 Soundness, of MARS, 235 SPADE, 127 SPEED algorithm, 127 Stanford Research Institute Problem Solver (STRIPS), 228 multiagent STRIPS-based planning, 229 Stanford-labeled dependency parser, 351 Statistical relational learning techniques, 292 Statistical–relational learning (SRL), 58 Stream mining, 127 Subgoals, Support Vector Machines (SVMs), 48, 90, 149, 316, 320, 325 play recognition using, 319 Surveillance setting, 356 Suspicious behavior, detecting, 110 air-combat environment, 112 catching a dangerous driver, 112 leaving unattended articles, 110 Symbolic Behavior Recognition (SBR), 87 anomalous behavior recognition for, 99 AVNET, 108 CAVIAR, 99 Symbolic plan-recognition system, 94–95 Synset, 45 Synthetic corpus, 10 Subject Index T V Team coordination, 321 automatic subgroup detection, 323 dynamic play adaptation, 325–326 Telemetry efforts, 290 Theory of mind (ToM), 177–179, 188 Theory-based Bayesian (TBB) framework, 181 3D scene, estimation of, 346 Tilted-time window model, 131 Top-level parameter recognition, 17 TrueBelief, 188 Value iteration algorithm, 279 for stochastic policy, 279 Variable matrix, 239 VirtualGold, 316 U Uncertain transitions at output level, 22 at prediction level, 22 Unification, 35 Unigram model, 305 Unlimited role-mapping model, 259 Upper Confidence bounds applied to Trees (UCT) search, 323, 292, 326, 329–331, 333 Utility-based plan-recognition (UPR) system, 87, 96 decomposition transition, 96 interruption, 96 observation probabilities, 96 sequential transition, 96 W Weighted abduction backward chaining, 35 based on integer linear programming, 33 cost function, 35 for discourse processing, 43 for plan recognition, 41 for recognizing textual entailment, 48 knowledge base, 44 NL pipeline, 44 overmerging, 46 unification, 35 Weighted fictitious play, 216 Weka J.48 classifier, 336 Wikipedia graph, 352 WordNet, 47 Wu’s weighting formula, 21 Y YOYO, 93 385 This page is intentionally left blank ... Geib Plan, Activity, and Intent Recognition (PAIR 2007) at the National Conference on Artificial Intelligence, AAAI-2007, organized by Christopher Geib and David Pynadath Plan, Activity, and Intent. .. with comparable intent- recognition capabilities Research addressing this area is variously referred to as plan recognition, activity recognition, goal recognition, and intent recognition This... and goal -recognition approaches; (2) activity discovery from sensory data; (3) modeling human cognitive processes; (4) multiagent systems; and (5) applications of plan, activity, and intent recognition