decision_control/slotplanner.cc

   1 /*
   2 This file is part of I am car.
   3
   4 I am car is free software: you can redistribute it and/or modify
   5 it under the terms of the GNU General Public License as published by
   6 the Free Software Foundation, either version 3 of the License, or
   7 (at your option) any later version.
   8
   9 I am car is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with I am car. If not, see <http://www.gnu.org/licenses/>.
  16 */
  17
  18 #include <algorithm>
  19 #include <cmath>
  20 #include <list>
  21 #include <queue>
  22 #include "slotplanner.h"
  23
  24 ParallelSlot::ParallelSlot()
  25 {}
  26
  27 // getter
  28 std::vector<std::vector<RRTNode *>> &ParallelSlot::cusp()
  29 {
  30         return this->cusp_;
  31 }
  32
  33 float ParallelSlot::DH() const
  34 {
  35         return this->DH_;
  36 }
  37
  38 PolygonObstacle &ParallelSlot::slot()
  39 {
  40         return this->slot_;
  41 }
  42
  43 float ParallelSlot::slotHeading()
  44 {
  45         float y0 = this->slot().bnodes()[0]->y();
  46         float x0 = this->slot().bnodes()[0]->x();
  47         float y3 = this->slot().bnodes()[3]->y();
  48         float x3 = this->slot().bnodes()[3]->x();
  49         float dy = y0 - y3;
  50         float dx = x0 - x3;
  51         return atan2(dy, dx);
  52 }
  53
  54 SlotSide ParallelSlot::slotSide()
  55 {
  56         return this->slotSide_;
  57 }
  58
  59 SlotType ParallelSlot::slotType()
  60 {
  61         return this->slotType_;
  62 }
  63
  64 // setter
  65 void ParallelSlot::DH(float dh)
  66 {
  67         this->DH_ = dh;
  68 }
  69
  70 void ParallelSlot::setAll()
  71 {
  72         // slot side
  73         float y0 = this->slot().bnodes()[0]->y();
  74         float x0 = this->slot().bnodes()[0]->x();
  75         float y1 = this->slot().bnodes()[1]->y();
  76         float x1 = this->slot().bnodes()[1]->x();
  77         float y3 = this->slot().bnodes()[3]->y();
  78         float x3 = this->slot().bnodes()[3]->x();
  79         if (sgn((x1 - x3) * (y0 - y3) - (y1 - y3) * (x0 - x3)) < 0)
  80                 this->slotSide_ = LEFT;
  81         else
  82                 this->slotSide_ = RIGHT;
  83         // slot type
  84         float d1 = EDIST(
  85                 this->slot().bnodes()[0],
  86                 this->slot().bnodes()[1]
  87         );
  88         float d2 = EDIST(
  89                 this->slot().bnodes()[1],
  90                 this->slot().bnodes()[2]
  91         );
  92         if (d1 > d2)
  93                 this->slotType_ = PERPENDICULAR;
  94         else
  95                 this->slotType_ = PARALLEL;
  96 }
  97
  98 // other
  99 void ParallelSlot::fip()
 100 {
 101         // see https://courses.cs.washington.edu/courses/cse326/03su/homework/hw3/bfs.html
 102         // RRTNode.s() works as iteration level
 103         std::queue<BicycleCar *, std::list<BicycleCar *>> q;
 104         std::queue<BicycleCar *, std::list<BicycleCar *>> empty;
 105         int di = -1;
 106         if (this->slotSide() == LEFT)
 107                 di = 1;
 108         BicycleCar *CC = this->getEPC();
 109         BicycleCar *B = this->getEP();
 110         this->DH(di * 0.01 / CC->out_radi());
 111         BicycleCar *c;
 112         int i = 0;
 113         c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 114         while (!this->slot().collide(c->frame())) {
 115                 q.push(c);
 116                 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 117                 i += 1;
 118         }
 119         delete c; // not in q and collide
 120         while (!q.empty()) {
 121                 c = q.front();
 122                 q.pop();
 123                 if (this->isInside(c)) {
 124                         goto createcuspandfinish;
 125                 } else if (c->s() < 9) {
 126                         BicycleCar *cc = this->flnc(c);
 127                         cc->s(c->s() + 1);
 128                         cc->bcparent(c);
 129                         q.push(cc);
 130                 } else {
 131                         delete c; // not in q and collide
 132                 }
 133         }
 134         std::swap(q, empty);
 135         return;
 136 createcuspandfinish:
 137         std::vector<RRTNode *> cusp;
 138         while (c) {
 139                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 140                 c = c->bcparent();
 141         }
 142         std::reverse(cusp.begin(), cusp.end());
 143         this->cusp().push_back(cusp);
 144         std::swap(q, empty);
 145 }
 146
 147 void ParallelSlot::fipr(BicycleCar *B)
 148 {
 149         std::vector<RRTNode *> cusp;
 150         cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
 151         int di = 1;
 152         if (this->slotSide() == LEFT)
 153                 di = -1;
 154         if (this->slotType() == PERPENDICULAR) {
 155                 this->DH(di * 0.01 / B->out_radi()); // TODO car in slot h()
 156                 RRTNode *cc;
 157                 if (this->slotSide() == LEFT)
 158                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 159                 else
 160                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 161                 BicycleCar *p;
 162                 int i = 1;
 163                 p = B->move(cc, i * this->DH());
 164                 while (
 165                         !this->slot().collide(p->frame())
 166                         && this->slot().collide(p)
 167                 ) {
 168                         delete p;
 169                         i += 10;
 170                         p = B->move(cc, i * this->DH());
 171                 }
 172                 i -= 10;
 173                 p = B->move(cc, i * this->DH());
 174                 while (
 175                         !this->slot().collide(p->frame())
 176                         && this->slot().collide(p)
 177                 ) {
 178                         delete p;
 179                         i += 1;
 180                         p = B->move(cc, i * this->DH());
 181                 }
 182                 i -= 1;
 183                 p = B->move(cc, i * this->DH());
 184                 cusp.push_back(new RRTNode(p->x(), p->y(), p->h()));
 185                 std::reverse(cusp.begin(), cusp.end());
 186                 this->cusp().push_back(cusp);
 187                 return;
 188         }
 189         this->DH(di * 0.01 / B->out_radi());
 190         BicycleCar *c;
 191         c = this->flncr(B);
 192         c->s(B->s() + 1);
 193         while ((
 194                 this->slotSide() == LEFT
 195                 && this->slot().collide(new RRTNode(c->lfx(), c->lfy(), 0))
 196         ) || (
 197                 this->slotSide() == RIGHT
 198                 && this->slot().collide(new RRTNode(c->rfx(), c->rfy(), 0))
 199         )) {
 200                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 201                 BicycleCar *cc = this->flncr(c);
 202                 cc->s(c->s() + 1);
 203                 delete c;
 204                 c = cc;
 205         }
 206         cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 207         std::reverse(cusp.begin(), cusp.end());
 208         this->cusp().push_back(cusp);
 209 }
 210
 211 BicycleCar *ParallelSlot::flnc(BicycleCar *B)
 212 {
 213         RRTNode *cc;
 214         if (this->slotSide() == LEFT) {
 215                 if (int(B->s()) % 2 == 0)
 216                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 217                 else
 218                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 219         } else {
 220                 if (int(B->s()) % 2 == 0)
 221                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 222                 else
 223                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 224         }
 225         BicycleCar *p;
 226         int i = 1;
 227         p = B->move(cc, i * this->DH());
 228         while (
 229                 !this->slot().collide(p->frame())
 230                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
 231         ) {
 232                 delete p;
 233                 i += 10;
 234                 p = B->move(cc, i * this->DH());
 235         }
 236         i -= 10;
 237         p = B->move(cc, i * this->DH());
 238         while (
 239                 !this->slot().collide(p->frame())
 240                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
 241         ) {
 242                 if (this->isInside(p)) {
 243                         i += 1;
 244                         break;
 245                 }
 246                 delete p;
 247                 i += 1;
 248                 p = B->move(cc, i * this->DH());
 249         }
 250         delete p;
 251         return B->move(cc, (i - 1) * this->DH());
 252 }
 253
 254 BicycleCar *ParallelSlot::flncr(BicycleCar *B)
 255 {
 256         RRTNode *cc;
 257         if (this->slotSide() == LEFT) {
 258                 if (int(B->s()) % 2 == 0)
 259                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 260                 else
 261                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 262         } else {
 263                 if (int(B->s()) % 2 == 0)
 264                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 265                 else
 266                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 267         }
 268         BicycleCar *p;
 269         int i = 1;
 270         p = B->move(cc, i * this->DH());
 271         while (
 272                 !this->slot().collide(p->frame())
 273                 && ((
 274                         this->slotSide() == LEFT
 275                         && this->slot().collide(new RRTNode(
 276                                 p->lfx(),
 277                                 p->lfy(),
 278                                 0
 279                         ))
 280                 ) || (
 281                         this->slotSide() == RIGHT
 282                         && this->slot().collide(new RRTNode(
 283                                 p->rfx(),
 284                                 p->rfy(),
 285                                 0
 286                         ))
 287                 ))
 288         ) {
 289                 delete p;
 290                 i += 10;
 291                 p = B->move(cc, i * this->DH());
 292         }
 293         i -= 10;
 294         p = B->move(cc, i * this->DH());
 295         while (!this->slot().collide(p->frame())) {
 296                 if(
 297                         this->slotSide() == LEFT
 298                         && !this->slot().collide(new RRTNode(
 299                                 p->lfx(),
 300                                 p->lfy(),
 301                                 0
 302                         ))
 303                 ) {
 304                         i += 1;
 305                         break;
 306                 }
 307                 if(
 308                         this->slotSide() == RIGHT
 309                         && !this->slot().collide(new RRTNode(
 310                                 p->rfx(),
 311                                 p->rfy(),
 312                                 0
 313                         ))
 314                 ) {
 315                         i += 1;
 316                         break;
 317                 }
 318                 i += 1;
 319                 p = B->move(cc, i * this->DH());
 320         }
 321         delete p;
 322         return B->move(cc, (i - 1) * this->DH());
 323 }
 324
 325 RRTNode *ParallelSlot::fposecenter()
 326 {
 327         return this->slot().bnodes().front();
 328 }
 329
 330 bool ParallelSlot::flast(
 331         RRTNode *P,
 332         bool right,
 333         int il,
 334         std::vector<RRTNode *> &cusp
 335 )
 336 {
 337         BicycleCar *B = new BicycleCar(P->x(), P->y(), P->h());
 338         RRTNode *cc;
 339         if (right)
 340                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 341         else
 342                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 343         BicycleCar *p;
 344         int i = 1;
 345         p = B->move(cc, i * this->DH());
 346         while (!this->slot().collide(p->frame())
 347                         && (
 348                                 (this->DH() > 0 && p->x() <= 0)
 349                                 || (this->DH() < 0 && p->x() >= 0)
 350                         )) {
 351                 delete p;
 352                 i += 10;
 353                 p = B->move(cc, i * this->DH());
 354         }
 355         i -= 10;
 356         p = B->move(cc, i * this->DH());
 357         while (!this->slot().collide(p->frame())
 358                         && (
 359                                 (this->DH() > 0 && p->x() <= 0)
 360                                 || (this->DH() < 0 && p->x() >= 0)
 361                         )) {
 362                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 363                         i += 1;
 364                         break;
 365                 }
 366                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 367                         i += 1;
 368                         break;
 369                 }
 370                 delete p;
 371                 i += 1;
 372                 p = B->move(cc, i * this->DH());
 373         }
 374         delete p;
 375         p = B->move(cc, (i - 1) * this->DH());
 376         if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 377                 cusp.push_back(p);
 378                 return true;
 379         } else if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 380                 cusp.push_back(p);
 381                 return true;
 382         } else if (il < 8) {
 383                 cusp.push_back(p);
 384                 return this->flast(p, !right, il + 1, cusp);
 385         }
 386         return false;
 387 }
 388
 389 void ParallelSlot::fpose()
 390 {
 391         bool left = false; // right parking slot
 392         float di = -1;
 393         BicycleCar *CC = new BicycleCar(
 394                 this->fposecenter()->x(),
 395                 this->fposecenter()->y() - 0.01,
 396                 this->slotHeading()
 397         );
 398         BicycleCar *B = new BicycleCar(
 399                 CC->x() - CC->width() / 2,
 400                 CC->y() - (CC->length() + CC->wheelbase()) / 2,
 401                 this->slotHeading()
 402         );
 403         if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
 404                 left = true;
 405                 di = 1;
 406                 delete B;
 407                 B = new BicycleCar(
 408                         CC->x() + CC->width() / 2,
 409                         CC->y() - (CC->length() + CC->wheelbase()) / 2,
 410                         this->slotHeading()
 411                 );
 412         }
 413         this->DH(di * 0.01 / CC->out_radi());
 414         BicycleCar *p;
 415         int i = 0;
 416         p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 417         while (!this->slot().collide(p->frame())) {
 418                 std::vector<RRTNode *> tmpcusp;
 419                 tmpcusp.push_back(new BicycleCar(p->x(), p->y(), p->h()));
 420                 if (this->flast(p, left, 0, tmpcusp)) {
 421                         this->cusp().push_back(tmpcusp);
 422                         return;
 423                 }
 424                 i += 1;
 425                 delete p;
 426                 p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 427         }
 428 }
 429
 430 BicycleCar *ParallelSlot::getEP()
 431 {
 432         // new pose for parallel parking to right slot
 433         float tnx;
 434         float tny;
 435         float nx;
 436         float ny;
 437         BicycleCar *CC = this->getEPC();
 438         // move left by car width / 2
 439         tnx = CC->x() + CC->width() / 2 * cos(CC->h() + M_PI / 2);
 440         tny = CC->y() + CC->width() / 2 * sin(CC->h() + M_PI / 2);
 441         if (this->slotSide() == LEFT) {
 442                 // move right by car width / 2
 443                 tnx = CC->x() + CC->width() / 2 * cos(CC->h() - M_PI / 2);
 444                 tny = CC->y() + CC->width() / 2 * sin(CC->h() - M_PI / 2);
 445         }
 446         if (this->slotType() == PARALLEL) {
 447                 // move down
 448                 nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
 449                 ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
 450         } else {
 451                 // move down
 452                 nx = tnx + (CC->length() - CC->wheelbase()) / 2 * cos(CC->h());
 453                 ny = tny + (CC->length() - CC->wheelbase()) / 2 * sin(CC->h());
 454         }
 455         return new BicycleCar(nx, ny, CC->h());
 456 }
 457
 458 BicycleCar *ParallelSlot::getEPC()
 459 {
 460         // new pose for parallel parking to right slot
 461         float ta;
 462         float nx;
 463         float ny;
 464         ta = this->slotHeading() + M_PI;
 465         if (this->slotSide() == RIGHT)
 466                 ta -= M_PI / 4;
 467         else
 468                 ta += M_PI / 4;
 469         nx = this->fposecenter()->x() + 0.01 * cos(ta);
 470         ny = this->fposecenter()->y() + 0.01 * sin(ta);
 471         return new BicycleCar(nx, ny, this->slotHeading());
 472 }
 473
 474 BicycleCar *ParallelSlot::getFP()
 475 {
 476         float x = this->slot().bnodes()[3]->x();
 477         float y = this->slot().bnodes()[3]->y();
 478         float h = this->slotHeading();
 479         float nx;
 480         float ny;
 481         if (this->slotType() == PARALLEL) {
 482                 if (this->slotSide() == LEFT) {
 483                         nx = x + BCAR_WIDTH / 2 * cos(h + M_PI / 2);
 484                         ny = y + BCAR_WIDTH / 2 * sin(h + M_PI / 2);
 485                 } else {
 486                         nx = x + BCAR_WIDTH / 2 * cos(h - M_PI / 2);
 487                         ny = y + BCAR_WIDTH / 2 * sin(h - M_PI / 2);
 488                 }
 489                 x = nx + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * cos(h);
 490                 y = ny + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * sin(h);
 491         } else {
 492                 if (this->slotSide() == LEFT) {
 493                         h -= M_PI / 2;
 494                         nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 495                                 * cos(h + M_PI);
 496                         ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 497                                 * sin(h + M_PI);
 498                         x = nx + (BCAR_DIAG_RRADI) * cos(h + M_PI / 2);
 499                         y = ny + (BCAR_DIAG_RRADI) * sin(h + M_PI / 2);
 500                 } else {
 501                         h += M_PI / 2;
 502                         nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 503                                 * cos(h - M_PI);
 504                         ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 505                                 * sin(h - M_PI);
 506                         x = nx + (BCAR_DIAG_RRADI) * cos(h - M_PI / 2);
 507                         y = ny + (BCAR_DIAG_RRADI) * sin(h - M_PI / 2);
 508                 }
 509         }
 510         return new BicycleCar(x, y, h);
 511 }
 512
 513 bool ParallelSlot::isInside(BicycleCar *c)
 514 {
 515         bool inside = true;
 516         RRTNode *tmpn;
 517         tmpn = new RRTNode(c->lfx(), c->lfy(), 0);
 518         if (!this->slot().collide(tmpn))
 519                 inside = false;
 520         delete tmpn;
 521         tmpn = new RRTNode(c->lrx(), c->lry(), 0);
 522         if (!this->slot().collide(tmpn))
 523                 inside = false;
 524         delete tmpn;
 525         tmpn = new RRTNode(c->rrx(), c->rry(), 0);
 526         if (!this->slot().collide(tmpn))
 527                 inside = false;
 528         delete tmpn;
 529         tmpn = new RRTNode(c->rfx(), c->rfy(), 0);
 530         if (!this->slot().collide(tmpn))
 531                 inside = false;
 532         delete tmpn;
 533         return inside;
 534 }
 535
 536 struct SamplingInfo ParallelSlot::getSamplingInfo()
 537 {
 538         struct SamplingInfo si;
 539         BicycleCar *CC = this->getEPC();
 540         si.x = this->slot().bnodes()[0]->x();
 541         si.y = this->slot().bnodes()[0]->y();
 542         if (this->slotSide() == RIGHT) {
 543                 si.dx = 1;
 544                 si.dy = 1;
 545                 si.dh = 1;
 546         } else {
 547                 si.dx = -1;
 548                 si.dy = -1;
 549                 si.dh = -1;
 550         }
 551         si.r = CC->diag_radi();
 552         si.sh = this->slotHeading();
 553         if (this->slotType() == PARALLEL) {
 554                 si.h = this->slotHeading() - acos(EDIST(
 555                         this->slot().bnodes()[0],
 556                         this->slot().bnodes()[1]
 557                 ) / BCAR_LENGTH);
 558         } else {
 559                 si.h = M_PI /2;
 560         }
 561         return si;
 562 }